Disconnected Forbidden Subgraphs, Toughness and Hamilton Cycles

In 1974, Goodman and Hedetniemi proved that every 2-connected -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 in 2-connected graphs can create only a trivial class of hamiltonian graphs (complete graphs) with . In this paper we prove that a single forbidden subgraph can create a non trivial class of hamiltonian graphs if is disconnected: every -free graph either is hamiltonian or belongs to a well defined class of non hamiltonian graphs; every 1-tough -free graph is hamiltonian. We conjecture that every 1-tough -free graph is hamiltonian and every 1-tough -free graph is hamiltonian. 1. Introduction Only finpite undiprected graphs without loops or multiple edges are considered. Let be a graph with vertex set and edge set . We write for the subgraph of induced by . The neighborhood of a vertex will be denoted by . We use to denote the number of vertices (order) of . The independence number of , denoted by , is the maximum size of an mutually nonadjacent vertices in . If are graphs then a graph is said to be —free if contains no copy of any of the graphs as an induced subgraph; the graphs will be also referred to in this context as forbidden subgraphs. We denote by and the path and the cycle on vertices. Further, denotes the complete graph of order , and denotes the complete bipartite graph with partite sets of cardinalities and . Specifically, the graph will be called a claw. The graph is obtained from by adding an edge. Let be the graph which is obtained by identifying each vertex of a triangle with an end vertex of one of three vertex-disjoint paths of lengths . Let denote the number of components of a graph . A graph is -tough if for every subset of the vertex set with . The toughness of , denoted , is the maximum value of for which is -tough (taking for all ). A good reference for any undefined terms is [1]. The first sufficient condition for hamiltonicity of a graph in terms of forbidden subgraphs is by Goodman and Hedetniemi [2]. Theorem A (see [2]). Every 2-connected -free graph is hamiltonian. This result gave rise to many other hamiltonicity conditions for various pairs and triples of forbidden connected subgraphs under