Hamilton-connected {claw, net}-free graphs, I

Xia Liu, Zdeněk Ryjáček*, Petr Vrána, Liming Xiong, Xiaojing Yang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

This is the first one in a series of two papers, in which we complete the characterization of forbidden generalized nets implying Hamilton-connectedness of a 3-connected claw-free graph. In this paper, we first develop the necessary techniques that allow one to handle the problem, namely:. (i) We strengthen the closure concept for Hamilton-connectedness in claw-free graphs, introduced by the second and third authors, such that not only the line graph preimage of a closure, but also its core has certain strong structural properties. (ii) We prove a special version of the “nine-point-theorem” by Holton et al. that allows one to handle Hamilton-connectedness of “small” (Formula presented.) -free graphs (where (Formula presented.) is the graph obtained by attaching endvertices of three paths of lengths (Formula presented.) to a triangle). (iii) By a combination of these techniques, as an application, we prove that every 3-connected (Formula presented.) -free graph is Hamilton-connected. The paper is followed by its second part in which we show that every 3-connected (Formula presented.) -free graph, where (Formula presented.), is Hamilton-connected. All the results on Hamilton-connectedness are sharp.

Original languageEnglish
Pages (from-to)154-179
Number of pages26
JournalJournal of Graph Theory
Volume102
Issue number1
DOIs
Publication statusPublished - Jan 2023

Keywords

  • Hamilton-connected
  • claw-free
  • closure
  • forbidden subgraph
  • net-free

Fingerprint

Dive into the research topics of 'Hamilton-connected {claw, net}-free graphs, I'. Together they form a unique fingerprint.

Cite this