کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4630284 | 1340597 | 2012 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fault tolerance of edge pancyclicity in alternating group graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The alternating group graph AGn was proposed as an interconnection network topology for computing systems. In this paper we study fault tolerant edge k-pancyclicity of AGn. A graph is edge k-pancyclic if for every edge eâG there is a cycle going through e of every length from k to |G|. Xue and Liu [Z.-J. Xue, S.-Y. Liu, An optimal result on fault-tolerant cycle-embedding in alternating group graphs, Inform. Proc. Lett. 109 (2009) 1197-1201] put the conjecture that AGn is (2n-8)-fault-tolerant edge 4-pancyclic, which means that if the number of faults |F|⩽2n-8, then AGn-F is still edge 4-pancyclic. Chang and Yang [J.-M. Chang, J.-S. Yang, Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput. 197 (2008) 760-767] showed that for the shortest cycles the fault-tolerance of AGn is much lower. They noted that with n-3 faults one can cut all 4-cycles going through a given edge e. On the other hand they showed that AGn is (n-4)-fault-tolerant edge 4-pancyclic. In this paper we show that the optimal upper bound of fault tolerance of edge 5-pancyclicity is equal to n-3 and it jumps up to 2n-7 for edge 6-pancyclicity (and edge k-pancyclicity, for every possible k⩾6).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 218, Issue 19, 1 June 2012, Pages 9875-9881
Journal: Applied Mathematics and Computation - Volume 218, Issue 19, 1 June 2012, Pages 9875-9881
نویسندگان
Andrzej Szepietowski,