2010/11/12 by Zdeněk Ryjáček, Petr Vrána · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #graph theory and CDMA systems #Multigraph #Combinatorics #Mathematics #Line graph #Social connectedness #Discrete mathematics #Cubic graph #Block graph #Quartic graph #Voltage graph #Graph #Pathwidth
paper · doi:10.1002/jgt.20498
openalex publication_date 2010/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
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