Search

In 1972 Chvátal gave a well-known sufficient condition for a graphical sequence to be forcibly Hamiltonian, and showed that in some sense his condition is best possible. In this paper, we conjecture that with probability 1 as Chvátal’s sufficient condition is also necessary. In contrast, we essentially prove that for every , the sufficient condition of Bondy and Boesch for forcible k-connectedness is not necessary in the same way.

We give a sufficient degree condition for the hamiltonicity of graphs with a 2-factor which is best possible in the same sense that Chvatal’s well-known hamiltonian degree condition is best possible.

In this survey we have attempted to bring together most of the results and papers that deal with toughness related to cycle structure. We begin with a brief introduction and a section on terminology and notation, and then try to organize the work into a few self explanatory categories. These categories are circumference, the disproof of the 2-tough conjecture, factors, special graph classes, computational complexity, and miscellaneous results as they relate to toughness. We complete the survey with some tough open problems!

It is proven that if G is a 3-cyclable graph on n vertices, with minimum degree δ and with a maximum independent set of cardinality α, then G contains a cycle of length at least min{n,3δ−3,n+δ−α}.

A cycle C of a graph G is a Dλ-cycle if every component of G-V(C) has order less than λ. Using the notion of Dλ-cycles, a number of results are established concerning long cycles in graphs with prescribed toughness and minimum degree. Let G be a t-tough graph on n ⩾ 3 vertices. If δ > n/(t + λ) + λ − 2 for some λ ⩽ t + 1, then G contains a Dλ-cycle. In particular, if δ > n/(t + 1) − 1, then G is hamiltonian, improving a classical result of Dirac for t > 1. If G is nonhamiltonian and δ > n/(t + λ) + λ − 2 for some λ ⩽ t + 1, then G contains a cycle of length at least (t + 1)(δ − λ + 2) + t, partially improving another classical result of Dirac for t > 1.

We show that recognizing 1-tough graphs is NP-hard, thereby settling a long-standing open problem. We also prove it is NP-hard to recognize t-tough graphs for any fixed positive rational number t.

Jung's theorem states that if G is a 1-tough graph on n ⩾11 vertices such that d ( x ) + d ( y )⩾ n −4 for all distinct nonadjacent vertices x , y , then G is hamiltonian. We give a simple proof of this theorem for graphs with 16 or more vertices.

We present (94−ε)-tough graphs without a Hamilton path for arbitrary ε>0, thereby refuting a well-known conjecture due to Chvátal. We also present (74−ε)-tough chordal graphs without a Hamilton path for any ε>0.

An embedding of graph G into graph H is by defenition an isomorphism of G onto a subgraph of H. It is shown in this paper that every unicycle U embeds in its line-graph L(U), and that every other connected graph that embeds in its own line-graph may be constructed from such an embedded unicycle in a natural way. A complete, explicit classification is also given of the graphs G that admit a special kind of embedding into L(G), called an incidence embedding. Moreover, the question of which graphs G are isomorphic to induced subgraphs G' of their line-graphs is shown to be formally equivalent to the original, more general question, where G' is not required to be induced.

Let G be a graph of order n , σ k = min{ ϵ i =1 k d ( ν i ): { ν 1 ,…, ν k } is an independent set of vertices in G }, NC = min{| N ( u )∪ N ( ν )|: uν ∉ E ( G )} and NC2 = min{| N ( u )∪ N ( ν )|: d ( u , ν )=2}. Ore proved that G is hamiltonian if σ 2 ⩾ n ⩾3, while Faudree et al. proved that G is hamiltonian if G is 2-connected and NC ⩾ 1 3 (2n−1) . It is shown that both results are generalized by a recent result of Bauer et al. Various other existing results in hamiltonian graph theory involving degree-sums or cardinalities of neighborhood unions are also compared in terms of generality. Furthermore, some new results are proved. In particular, it is shown that the bound 1 3 (2n−1) on NC in the result of Faudree et al. can be lowered to 1 3 (2n−1) , which is best possible. Also, G is shown to have a cycle of length at least min{ n , 2(NC2)} if G is 2-connected and σ 3 ⩾ n +2. A D λ -cycle ( D λ -path) of G is a cycle (path) C such that every component of G − V ( C ) has order smaller than λ. Sufficient conditions of Lindquester for the existence of Hamilton cycles and paths involving NC2 are extended to D λ -cycles and D λ -paths.