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 is not an element of {K-8 - E(K-4), K-10 - 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. (C) 2013 Elsevier Inc. All rights reserved.