Mathematika

Table of Contents - June 1971 - Volume 18, Issue 01  

Research Article

Trees with Hamiltonian square

Frank Hararya1 and Allen Schwenka2

a1 University of Michigan.

a2 University of Waterloo.

Plummer (see [2; p. 69]) conjectured that the square of every block is hamiltonian, and this has just been proved by Fleischner [1]. It was shown by Karaganis [3] that the cube of every connected graph, and hence the cube of every tree, is hamiltonian. Our present object is to characterize those trees whose square is hamiltonian in three equivalent ways.

We follow the terminology and notation of the book [2]. In particular, the following concepts are used in stating our main result. A graph is hamiltonian if it has a cycle containing all its points. The graph with the same points as G, in which two points are adjacent if their distance in G is at most 2, is denoted by G2 and is called the square of G. The subdivision graph S(G) is formed (Figure 1) by inserting a point of degree two on each line of G.

(Received March 22 1971)

Key Words:

  • 05C05 Combinatorics: Graph theory; Trees.;
  • O5C35 Combinatorics: Graph theory: Paths.