- Title
- A Closure for 1-Hamilton-Connectedness in Claw-Free Graphs
- Creator
- Ryjáček, Zdeněk; Vrána, Petr
- Relation
- Journal of Graph Theory Vol. 75, Issue 4, p. 358-376
- Publisher Link
- http://dx.doi.org/10.1002/jgt.21743
- Publisher
- Wiley Blackwell Publishing
- Resource Type
- journal article
- Date
- 2014
- Description
- 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.
- Identifier
- http://hdl.handle.net/1959.13/1067584
- Identifier
- uon:18443
- Identifier
- ISSN:1097-0118
- Language
- eng
- Reviewed
- Hits: 1351
- Visitors: 1312
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|