zbMATH — the first resource for mathematics

Hamiltonian connected hourglass free line graphs. (English) Zbl 1147.05045
Summary: C. Thomassen [Reflections on graph theory, J. Graph Theory 10, 309–324 (1986; Zbl 0614.05050)] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to \(K_{5}-E(C_{4})\), where \(C_{4}\) is a cycle of length 4 in \(K_{5}\). In [H. J. Broersma, M. Kriesell, and Z. Ryjácek, On factors of 4-connected claw-free graphs, J. Graph Theory 37, No. 2, 125–136 (2001; Zbl 0984.05067)] it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Elsevier New York · Zbl 1134.05001
[2] Broersma, H.J.; Kriesell, M.; Ryjác˘ek, Z., On factors of 4-connected claw-free graphs, J. graph theory, 37, 125-136, (2001) · Zbl 0984.05067
[3] Lai, H.-J.; Li, X.; Ou, Y.; Poon, H., Spanning trails joining given edges, Graph combinator, 21, 1, 77-88, (2005) · Zbl 1061.05054
[4] H.-J. Lai, Y. Shao, G. Yu, M. Zhan, Hamiltonian connectedness in 3-connected line graphs, submitted for publication. · Zbl 1169.05344
[5] Ryjác˘ek, Z., On a closure concept in claw-free graphs, J. combin. theory ser. B, 70, 217-224, (1997) · Zbl 0872.05032
[6] Y. Shao, Hamiltonian claw-free graphs, Ph.D. Dissertation, West Virginia University, 2005. · Zbl 1060.05061
[7] Thomassen, C., Reflections on graph theory, J. graph theory, 10, 309-324, (1986) · Zbl 0614.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.