Hamiltonian connectedness in 3-connected line graphs
We investigate graphs G G such that the line graph L(G) L ( G ) is hamiltonian connected if and only if L(G) L ( G ) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G G , then L(G) L ( G ) has the above mentioned property. Our result extends Kriesells recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306315] 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) L ( G ) does not have an hourglass (a graph isomorphic to K5?E(C4) K 5 ? E ( C 4 ) , where C4 C 4 is an cycle of length 4 in K5 K 5 ) as an induced subgraph, and if every 3-cut of L(G) L ( G ) is not independent, then L(G) L ( G ) is hamiltonian connected if and only if ?(L(G))?3 ? ( L ( G ) ) ? 3 , which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306315] that every 4-connected hourglass free line graph is hamiltonian connected.
hamiltonian connected collapsible graphs core graphs