A necessary and sufficient condition for connected, locally k-connected k1,3-free graphs to be k-hamiltonian

✍ Scribed by Zhou Huai-Lu

• Publisher: John Wiley and Sons
• Year: 1989
• Tongue: English
• Weight: 272 KB
• Volume: 13
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190130602

✦ Synopsis

We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K,,-free graph is k-hamiltonian if and only if it is (k + 2)-connected ( k L 1).

We use [ 11 for basic terminology and notation, and consider simple graphs only. Let G be a graph. By V(G) and E(G) we denote, respectively, the vertex set and edge set of

hamiltonian for every subset S of V(G) with 0 5 IS1 5 k. The distance along a cycle C between two distinct vertices x ,y E V ( C ) ,denoted by d,(x,y), is the length of the shortest (x,y)-section of c.

We prove the following result, which was conjectured by Broersma and Veldman [2]: Theorem 1.

(k 2 1). Then G is k-hamiltonian if and only if G is (k + 2)-connected.

Let G be a connected, locally k-connected K,,,-free graph