Disconnected Forbidden Subgraphs, Toughness and Hamilton Cycles. (10th March 2013)

• Record Type: Journal Article
• Authors: Nikoghosyan, Zh. G.
• Other Names: Alekseyev M. Academic Editor.; Eliasi M. Academic Editor.; Gordon N. A. Academic Editor.; Kelarev A. V. Academic Editor.; Lin C.-K. Academic Editor.; Protasov V. Y. Academic Editor.; Zhang Y. Academic Editor.
• Is Part Of: ISRN combinatorics. Volume 2013(2013)
• Publication Date: 2013-03-10
• Subjects: Combinatorial analysis -- Periodicals; Combinatorial analysis; Electronic journals; Periodicals; 511.6
• DOI: 10.1155/2013/673971
• Languages: English
• ISSNs: 2090-8911

Abstract

Abstract : In 1974, Goodman and Hedetniemi proved that every 2-connected ( K 1, 3, K 1, 3 + e ) -free graph is hamiltonian. This result gave rise many other conditions for Hamilton cycles concerning various pairs and triples of forbidden connected subgraphs under additional connectivity conditions. In this paper we investigate analogous problems when forbidden subgraphs are disconnected which affects more global structures in graphs such as tough structures instead of traditional connectivity structures. In 1997, it was proved that a single forbidden connected subgraph R in 2-connected graphs can create only a trivial class of hamiltonian graphs (complete graphs) with R = P 3 . In this paper we prove that a single forbidden subgraph R can create a non trivial class of hamiltonian graphs if R is disconnected: ( ∗ 1 ) every ( K 1 ∪ P 2 ) -free graph either is hamiltonian or belongs to a well defined class of non hamiltonian graphs; ( ∗ 2 ) every 1-tough ( K 1 ∪ P 3 ) -free graph is hamiltonian. We conjecture that every 1-tough ( K 1 ∪ P 4 ) -free graph is hamiltonian and every 1-tough P 4 -free graph is hamiltonian.