Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs

Abstract

We introduce a closure concept that turns a claw-free graph into the line graph of a multigraph while preserving its (non-)Hamilton-connectedness. As an application, we show that every 7-connected claw-free graph is Hamilton-connected, and we show that the well-known conjecture by Matthews and Sumner (every 4-connected claw-free graph is hamiltonian) is equivalent with the statement that every 4-connected claw-free graph is Hamilton-connected. Finally, we show a natural way to avoid the non-uniqueness of a preimage of a line graph of a multigraph, and we prove that the closure operation is, in a sense, best possible. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:152-173, 2011