Conditional fault hamiltonian connectivity of the complete graph

Tung-Yang Ho, Yuan-Kang Shih, Jiann-Mean Tan, Lih-Hsing Hsu

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by B(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G - F is hamiltonian connected for every F C E(G) with |F| <= k and S(G - F) >= 3. The conditional edge-fault tolerant hamiltonian connectivity HCe3(G) is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n >= 4. We use K-n to denote the complete graph with n vertices. In this paper, we show that HCe3(K-n) = 2n - 10 for n is not an element of {4, 5, 8, 10}, HCe3 (K-4) = 0, HCe3 (K-5) = 2, HCe3(K-8) = 5, and HCe3(K-10) = 9. (c) 2009 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)585-588
Number of pages4
JournalInformation Processing Letters
Issue number12
StatePublished - 31 May 2009


  • Complete graph; Hamiltonian; Hamiltonian connected; Fault tolerance

Fingerprint Dive into the research topics of 'Conditional fault hamiltonian connectivity of the complete graph'. Together they form a unique fingerprint.

Cite this