کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
393747 665683 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Maximally local connectivity and connected components of augmented cubes
ترجمه فارسی عنوان
حداکثر اتصال محلی و اجزای متصل از مکعب های تکمیل شده
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی

The connectivity of a graph is an important issue in graph theory, and is also one of the most important factors in evaluating the reliability and fault tolerance of a network. It is known that the augmented cube  AQnAQn is maximally connected  , i.e. (2n-1)(2n-1)-connected, for n⩾4n⩾4. By the classic Menger’s Theorem  , every pair of vertices in AQnAQn is connected by 2n-12n-1vertex-disjoint paths   for n⩾4n⩾4. A routing with parallel paths can speed up transfers of large amounts of data and increase fault tolerance. Motivated by research on networks with faults, we obtained the result that for any faulty vertex set F⊂V(AQn)F⊂V(AQn) and |F|⩽2n-7|F|⩽2n-7 for n⩾4n⩾4, each pair of non-faulty vertices, denoted by u and v  , in AQn-FAQn-F is connected by min{degf(u),degf(v)}min{degf(u),degf(v)} vertex-disjoint fault-free paths, where degf(u)degf(u) and degf(v)degf(v) are the degree of u and v   in AQn-FAQn-F, respectively. Moreover, we demonstrate that for any faulty vertex set F⊂V(AQn)F⊂V(AQn) and |F|⩽4n-9|F|⩽4n-9 for n⩾4n⩾4, there exists a large connected component with at least 2n-|F|-12n-|F|-1 vertices in AQn-FAQn-F, which improves on the results of Ma et al. (2008) who show this for n⩾6n⩾6.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 273, 20 July 2014, Pages 387–392
نویسندگان
, , ,