Hamiltonian connected hourglass free line graphs. (English) Zbl 1147.05045

Dengxin, Li; Lai, Hong-Jian; Shao, Yehong; Zhan, Mingquan

Discrete Math. 308, No. 12, 2634-2636 (2008).

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.

MSC:

05C45

Eulerian and Hamiltonian graphs

Keywords:

Hamiltonian connected graph; line graph; hourglass free graph; hourglass; hourglass free line graph

References:

[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