Panconnectivity of locally connected claw-free graphs
A graph \(G\) is claw-free if \(G\) does not contain an induced subgraph isomorphic to \(K_{1,3}\). A graph \(G\) is locally connected if, for every vertex \(v\) of \(G\), the subgraph of \(G\) induced by \(N(v)\) is connected. The main result is as follows. Let \(G\) be a connected, locally connected, claw-free graph and let \(x, y\) be two vertices of \(G\). If \(T \cap \{ x, y \} = \varnothing\) for every 2-cut \(T\) of \(G\), then the graph \(G\) contains \((x,y)\)-paths of all possible lengths \(h\): \(d(x,y) \leq h \leq |V(G)|- 1\), where \(d(x,y)\) is the distance between the vertices \(x\) and \(y\). This result implies a conjecture by \textit{H. J. Broersma} and \textit{H. J. Veldman} [J. Graph Theory 11, No. 3, 399-407 (1987; Zbl 0656.05045)] that every 3-connected, locally connected, claw-free graph of order at least four contains a Hamilton circuit.
scientific article; zbMATH DE number 1334490
scientific article