zbMATH — the first resource for mathematics

Hamiltonian connectedness in 3-connected line graphs. (English) Zbl 1169.05344
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.

05C40 Connectivity
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI
[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
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.