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