𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Zdeněk Ryjáček; Petr Vrána

Book ID
102892032
Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
958 KB
Volume
66
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

We introduce a closure concept that turns a claw-free graph into the line graph of a multigraph while preserving its (non-)Hamiltonconnectedness. 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.

📜 SIMILAR VOLUMES

Hamilton connectivity of line graphs and
Hamilton connectivity of line graphs and claw-free graphs
✍ Zhiquan Hu; Feng Tian; Bing Wei 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract Let __G__ be a graph and let __V__~0~ = {ν∈ __V__(__G__): __d__~__G__~(ν) = 6}. We show in this paper that: (i) if __G__ is a 6‐connected line graph and if |__V__~0~| ≤ 29 or __G__[__V__~0~] contains at most 5 vertex disjoint __K__~4~'s, then __G__ is Hamilton‐connected; (ii) every 8‐co

On stability of Hamilton-connectedness u
On stability of Hamilton-connectedness under the 2-closure in claw-free graphs
✍ Zdeněk Ryjáček; Petr Vrána 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 1 views

We show that, in a claw-free graph, Hamilton-connectedness is preserved under the operation of local completion performed at a vertex with 2-connected neighborhood. This result proves a conjecture by Bollobás et al.