Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs

Y-Chuang Chen, Yong-Zen Huang, Lih Hsing Hsu, Jiann-Mean Tan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

A k-regular hamiltonian and hamiltonian connected graph G is optimal fault-tolerant hamiltonian and hamiltonian connected if G remains hamiltonian after removing at most k - 2 nodes and/or edges and remains hamiltonian connected after removing at most k - 3 nodes and/or edges. In this paper, we investigate a construction scheme to construct optimal fault-tolerant hamiltonian and hamiltonian connected graphs. Hence, some of the generalized hypercubes, Twisted-cubes, Crossed-cubes, and Mobius cubes are optimal fault-tolerant hamiltonian and optimal fault-tolerant hamiltonian connected.
Original languageEnglish
Title of host publicationInternational Electronic Conference on Computer Science
Pages344-346
Number of pages3
Volume1060
StatePublished - 2008

Keywords

  • Twisted-cubes; Crossed-cubes; Mobius cubes; generalized hypercubes; recursive circulant graphs; optimal fault-tolerant
  • GENERALIZED HYPERCUBE; NETWORKS; CUBES

Fingerprint Dive into the research topics of 'Optimal Fault-Tolerant Hamiltonian and Hamiltonian Connected Graphs'. Together they form a unique fingerprint.

Cite this