Originators: Vaclav Chátal; Guantao Chen, Michael Jacobson, André Kézdy, Jenö Lehel (presented by Paul Wenger - REGS 2008)
Definitions: A graph G is t-tough if |S| ≥ t μ(G-S) for every separating set S, where μ(G-S) denotes the number of components of G-S. The toughness of a graph G is the maximum t such that G is t-tough. A survey on the properties of toughness and t-tough graphs appears in [BBS].
Background: Chvátal introduced toughness in 1973 and conjectured that there exists a t such that all t-tough graphs are Hamiltonian. It was thought for some time that toughness 2 was sufficient, but this was disproved in [BBV], which presented non-Hamiltonian graphs with toughness approaching 9/4. (Chvátal's original guess of 3/2 was disproved by Thomassen.) This problem asks for toughness thresholds that ensure Hamiltonian cycles for graphs in various special families.
Definitions: A graph is chordal if it has no induced subgraph that is a cycle of length at least 4. Chordal graphs equivalently are those built from K1 by iteratively adding a vertex made adjacent to a clique. A chordal graph has clique number at most k if the neighborhood of the new vertex always has size less than k. It is a k-tree if after starting with Kk the neighborhood of the new vertex is always a k-clique.
Alternatively, a graph is chordal if and only if it is the intersection graph of a family of subtrees of a tree. When the tree is restricted to be a path, the resulting graphs are the interval graphs. When the tree is a subdivision of a star, the resulting graphs have analogously been called spider graphs (since subdivisions of stars are called spiders), but spider intersection graphs would be clearer. Similarly, when the host tree is a caterpillar, one could call the resulting chordal graphs caterpillar intersection graphs.
A graph is a split graph if its vertex set can be partitioned into a clique and an independent set; split graphs are chordal; equivalently, it is the intersection graph of a family of subtrees of a star. A graph is strongly chordal if it is chordal and every even cycle with length at least 6 has a chord joining vertices separated by even distance along the cycle.
Question 1: What is the minimum t such that every t-tough chordal graph is Hamiltonian?
Comments: Although Chvátal's Conjecture remains open in general, Chen, Jacobson, Kézdy, and Lehel [CJKL] proved that 18-tough chordal graphs are Hamiltonian. In other words, the answer to Question 1 exists and is at most 18. Bauer, Broersma and Veldman [BBV] showed that for ε>0 there are chordal graphs with toughness 7/4-ε that are not Hamiltonian, so the answer to the Question is at least 7/4. It is conjectured that the answer is 2.
Question 2: What improved bounds on the value of toughness that suffices for Hamiltonicity can be obtained for special families of chordal graphs? Candidates include k-trees, chordal graphs with clique number at most k, interval graphs, spider graphs, split graphs, and strongly chordal graphs.
Comments: Broersma, Xiong, and Yoshimoto [BXY] proved that k-trees with toughness at least (k+1)/3 are Hamiltonian (for k≥2). For the lower bound, they show only that for k≥3 there are infinite classes of 1-tough k-trees that are not Hamiltonian. Chordal graphs with clique number at most k+1 are a natural more general family in which to study this question.
Keil [K] proved that toughness 1 is both necessary and sufficient for interval graphs. Using this result in a matroidal proof, Kaiser, Kral, and Stacho [KKS] proved for the more general family of spider intersection graphs that t=3/2 is the smallest toughness threshold to guarantee spanning cycles. They also gave an alternative proof of the result of Kratsch, Lehel, and Müller [KLM] that t=3/2 is the smallest toughness threshold to guarantee spanning cycles for split graphs.
Since interval graphs are the graphs that are both chordal and complements of comparability graphs, another direction in which to extend the result of Keil [K] is to consider cocomparability graphs. Deogun, Kratsch, and Steiner [DKS] strengthened the result of [K] by proving that 1-tough cocomparability graphs are Hamiltonian.
Also, Böhme, Harant, and Tkác [BHT] proved that chordal planar graphs with toughness more than 1 are planar, but that among chordal planar graphs with toughness 1 there are graphs whose longest cycle is an arbitrarily small fraction of the number of vertices. Finally, for claw-free graphs the toughness is exactly half the connectivity [MS], so the connecture that toughness 2 suffices is equivalent to the conjecture that 4-connected claw-free graphs are Hamiltonian.
There appear as yet to be no results on the optimal toughness thresholds for chordal graphs with clique number k, for caterpillar intersection graphs, for intersection graphs of trees with diameter at most 3 or at most 4 (split graphs are the intersection graphs of trees with diameter 2), or for strongly chordal graphs.
References:
[BBS] Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward; Toughness in
graphs---a survey. Graphs Combin. 22 (2006), no. 1, 1--35.
[BBV] Bauer, D.; Broersma, H. J.; Veldman, H. J.; Not every 2-tough graph is Hamiltonian. Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997). Discrete Appl. Math. 99 (2000), no. 1-3, 317--321.
[BHT] Böhme, Thomas; Harant, Jochen; Tká\v c, Michal;
More than one tough chordal planar graphs are Hamiltonian. (English summary)
J. Graph Theory 32 (1999), no. 4, 405--410.
[BXY] Broersma, Hajo; Xiong, Liming; Yoshimoto, Kiyoshi; Toughness and
Hamiltonicity in k-trees. Discrete Math. 307 (2007), no. 7-8,
832--838.
[CJKL] Chen, Guantao; Jacobson, Michael S.; Kézdy, André E.;
Lehel, Jenö; Tough
enough chordal graphs are Hamiltonian. Networks 31 (1998), no. 1, 29--38.
[DKS] Deogun, Jitender S.; Kratsch, Dieter; Steiner, George
1-tough cocomparability graphs are Hamiltonian.
Discrete Math. 170 (1997), no. 1-3, 99--106.
[KLM] D. Kratsch, J. Lehel and H. Müller, Discrete Math. 150 (1996), no.
1-3, 231--245.
[KKS] Kaiser, Tomá\v s; Král, Daniel; Stacho, Ladislav;
Tough spiders. J. Graph Theory 56 (2007), no. 1, 23--40.
[K] J. M. Keil; Finding hamiltonian circuits in interval graphs, Inf Proc Let 20
(1985), pp. 201--206.
[MS] Matthews, M. M.; Sumner, D. P. Hamiltonian results in
K1,3-free graphs.
J. Graph Theory 8 (1984), no. 1, 139--146.