Edge-fault-tolerant panconnectivity and edge-pancyclicity of the complete graph

The complete graphs are an important class of graphs, and are also fundamental interconnection networks. Recently, Fu investigated their edge-fault-tolerant Hamiltonicity and Ho et al. investigated their edge-fault-tolerant Hamiltonian-connectivity. In this paper, we improve the result of Fu and point out that the proof of the result of Ho et al. fails. Then we consider the edge-fault-tolerant panconnectivity of the complete graphs and obtain the following result. Let F be any set of at most 2n-10 faulty edges in the complete graph K"n with n vertices, such that every vertex of the graph G=K"n-F is incident with at least three edges and G@?{K"8-E(K"4),K"1"0-E(K"5)}. Then G is nearly panconnected, i.e., for any two vertices u and v, there exists a path connecting u and v in G of any length from 3 to n-1. As a corollary, every edge in the graph G lies on a cycle of any length from 4 to n. Moreover, the number 2n-10 of faulty edges tolerated is sharp.