Originators:M. Bilinski, J. Ma, X. Yu (presented by H. Wu - REGS 2010)
Definitions: The circumference of a graph G, written c(G), is the maximum length of a cycle in G. A graph is claw-free if it has no induced subgraph isomorphic to K1,3. A graph is essentially-k-connected if any separating set that does not isolate a single vertex has size at least k.
Background: Barnette[2] proved that every 3-connected n-vertex cubic graph has circumference &Omega(log2 n). Bondy and Simonovits [3] improved this bound to e&Omega(√log2 n). They also constructed an infinite family of 3-connected n-vertex cubic graphs with circumference &Theta(nlog98) (≈0.946). They conjectured that the lower bound should be &Omega(nc) for some constant c between 0 and 1. This conjecture was proved by Jackson [5], with c=log2(1+√5)-1, which is about 0.69.
For the circumference of claw-free graphs, Broersma, Van den Heuvel, Jung and Veldman [4] showed that the circumference of a 2-connected claw-free n-vertex graph is Ω(logn). Bilinski, Ma and Yu [4] proved that the circumference of a 3-connected claw-free graph is &Omega(log32). At the 2010 SIAM conference on Discrete Mathematics, they announced an improvement to &Omega(nlog2(1+√5)-1).
Conjecture 1:(Thomassen [9]) Every 4-connected line graph is Hamiltonian.
Conjecture 2:(Mathews & Sumner[7]) Every 4-connected claw-free graph is Hamiltonian.
Comments:Ryjacek [8] showed that the above two conjectures are equivalent. So far the best result is that 7-connected line graphs contain Hamilton cycles, due to Zhan [10]. Also, Lai, Shao, Wu and Zhou [5] proved that every 3-connected essentially-11-connected claw-free graph is Hamiltonian.
Problem 3:Reduce the gap between &Omega(nlog2(1+√5)-1) and &Omega(nlog9 8) for the lower bound on the circumference of 3-connected n-vertex claw-free graphs.
References:
[1] M. Bilinski, M. Ma, X. Yu, Bounding the circumference of 3-connected claw-free graphs. (Preprint).
[2] D. Branette, Trees in polyhedral graphs, Cannad. J. Math. 18 (1966) 731-736.
[3] J.A. Bondy and M. Simonovits, Longest cycles in 3-connected cubic graphs, Canad. J. Math.32 (1980) 987-992.
[4] H.J.Broersma, J. Van Den Heuvel, H.A. Jung and H.J> Veldman, Long paths and cycles in tough graphs, Graphs Combin. 9 (1993) 3-17.
[5] H.J Lai, Y. Shao, H. Wu and J.Zhou, Every 3-connected, essentially 11-connected line graph is Hamiltonian. J. Combin. Theory Ser. B 96 (2006), no. 4,
571--576.
[6] B. Jackson, Longest cycles in 3-connected cubic graphs, J. Combin. Theory Ser. B 41(1986) 17-26.
[7] M.M. Mathews and D. P. Sumner, Hamiltonain results in K1,3-free graphs, J. Graph Theory 8 (1984) 139-146.
[8] Z. Ryjacek, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224.
[9] C. Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309-324.
[10] S. Zhan, On hamiltonian line graphs and connectivity, Discrete Math. 89 (1991) 89-95.