Premium
A Closure for 1‐Hamilton‐Connectedness in Claw‐Free Graphs
Author(s) -
Ryjáček Zdeněk,
Vrána Petr
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21743
Subject(s) - mathematics , combinatorics , multigraph , line graph , critical graph , quartic graph , discrete mathematics , social connectedness , distance hereditary graph , graph power , graph , psychology , psychotherapist
A graph G is 1‐Hamilton‐connected if G − x is Hamilton‐connected for every vertex x ∈ V ( G ) . In the article, we introduce a closure concept for 1‐Hamilton‐connectedness in claw‐free graphs. If G ¯ is a (new) closure of a claw‐free graph G , then G ¯ is 1‐Hamilton‐connected if and only if G is 1‐Hamilton‐connected, G ¯ is the line graph of a multigraph, and for some x ∈ V ( G ) ,G ¯ − x is the line graph of a multigraph with at most two triangles or at most one double edge. As applications, we prove that Thomassen's Conjecture (every 4‐connected line graph is hamiltonian) is equivalent to the statement that every 4‐connected claw‐free graph is 1‐Hamilton‐connected, and we present results showing that every 5‐connected claw‐free graph with minimum degree at least 6 is 1‐Hamilton‐connected and that every 4‐connected claw‐free and hourglass‐free graph is 1‐Hamilton‐connected.