Hamiltonian connectedness in 3-connected line graphs. (English) Zbl 1169.05344

Lai, Hong-Jian; Shao, Yehong; Yu, Gexin; Zhan, Mingquan

Discrete Appl. Math. 157, No. 5, 982-990 (2009).

Summary: We investigate graphs \(G\) such that the line graph \(L(G)\) is hamiltonian connected if and only if \(L(G)\) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of \(G\), then \(L(G)\) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, ”All 4-connected line graphs of claw free graphs are Hamiltonian-connected,” J. Comb. Theory, Ser. B 82, No. 2, 306–315 (2001; Zbl 1027.05059)] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if \(L(G)\) does not have an hourglass (a graph isomorphic to \(K_{5} - E(C_{4})\), where \(C_{4}\) is a cycle of length 4 in \(K_{5}\)) as an induced subgraph, and if every 3-cut of \(L(G)\) is not independent, then \(L(G)\) is hamiltonian connected if and only if \(\kappa (L(G))\geq 3\), which extends a recent result by Kriesell [cited above] that every 4-connected hourglass free line graph is hamiltonian connected.

MSC:

05C40	Connectivity
05C45	Eulerian and Hamiltonian graphs

Keywords:

Hamiltonian connected; collapsible graphs; core graphs; hourglass

References:

[1]	Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan London, Elsevier, New York · Zbl 1134.05001
[2]	Catlin, P.A., Supereulerian graphs: A survey, J. graph theory, 16, 177-196, (1992) · Zbl 0771.05059
[3]	Catlin, P.A., The reduction of graph families closed under contraction, Discrete math., 160, 67-80, (1996) · Zbl 0867.05081
[4]	Catlin, P.A., A reduction method to find spanning Eulerian subgraphs, J. graph theory, 12, 29-44, (1988) · Zbl 0659.05073
[5]	Catlin, P.A.; Han, Z.-Y; Lai, H.-J., Graphs without spanning closed trails, Discrete math., 160, 81-91, (1996) · Zbl 0859.05060
[6]	Catlin, P.A.; Hobbs, A.M.; Lai, H.-J., Operations and graph families, Discrete math., 230, 71-98, (2001)
[7]	Catlin, P.A.; Lai, H.-J., Spanning trails joining two given edges, (), 207-222 · Zbl 0841.05067
[8]	Harary, F.; Nash-Williams, C.St.J.A., On eulerian and Hamiltonian graphs and line graphs, Canad. math. bull., 8, 701-709, (1965) · Zbl 0136.44704
[9]	Kriesell, M., All 4-connected line graphs of claw free graphs are Hamiltonian-connected, J. combin. theory ser. B, 82, 306-315, (2001) · Zbl 1027.05059
[10]	Thomassen, C., Reflections on graph theory, J. graph theory, 10, 309-324, (1986) · Zbl 0614.05050
[11]	Zhan, S., Hamiltonian connectedness of line graphs, Ars combinatoria, 22, 89-95, (1986) · Zbl 0611.05038