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).