Hamilton‐connected {claw, net}‐free graphs, I
Xia Liu, Zdeněk Ryjáček, Petr Vrána, Liming Xiong, Xiaojing Yang · Journal of Graph Theory · 2022
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” { K 1 , 3 , N i , j , k } $\{{K}_{1,3},{N}_{i,j,k}\}$ -free graphs (where N i , j , k ${N}_{i,j,k}$ is the graph obtained by attaching endvertices of three paths of lengths i , j , k $i,j,k$ to a triangle). (iii) By a combination of these techniques, as an application, we prove that every 3-connected { K 1 , 3 , N 1 , 3 , 3 } $\{{K}_{1,3},{N}_{1,3,3}\}$ -free graph is Hamilton-connected. The paper is followed by its second part in which we show that every 3-connected { K 1 , 3 , X } $\{{K}_{1,3},X\}$ -free graph, where X ∈ { N 1 , 1 , 5 , N 2 , 2 , 3 } $X\in \{{N}_{1,1,5},{N}_{2,2,3}\}$ , is Hamilton-connected. All the results on Hamilton-connectedness are sharp.