The square of a connected S(K1,3)-free graph is vertex pancyclic

✍ Scribed by George Hendry; Walter Vogler

• Publisher: John Wiley and Sons
• Year: 1985
• Tongue: English
• Weight: 129 KB
• Volume: 9
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190090415

✦ Synopsis

We prove the conjecture of Gould and Jacobson that a connected S(K1,J free graph has a vertex pancyclic square. Since .S(K1,J is not vertex pancyclic, this result is best possible.

Our notation generally follows that used in [l]

. A graph G is Hamilroniun if it contains a cycle through all its vertices. G is vertex pancyclic if each of its vertices lies on a cycle of each length I, 3 S 1 S /V(G)I. The square of G, denoted GZ, is the graph with vertex set V(G) in which two vertices are adjacent if their distance in G is one or two. The graph S(K,,,) is K1,3 with each edge subdivided once. A graph is H-free if it does not contain an induced subgraph

The major result about Harniltonian squares is due to Fleischner [2]: the square of a 2-connected graph is Hamiltonian. Furthermore, he proved [31 that in the square of a graph, the properties of being Harniltonian and being vertex pancyclic are equivalent. It has been shown [5] that the square of a tree T is Hamiltonian if and only if T is S(Kl,J-free. Recently Matthews and Sumner (61 showed that the square of a connected Kl,3-free graph is vertex pancyclic and Gould and Jacobson [4] improved this in several ways. The latter conjectured that the square of a connected S(K,,J-free graph is vertex pancyclic, which in turn improves their results. We prove this making use of [2,3] and the proof of