Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-06T07:13:03.665Z Has data issue: false hasContentIssue false

Trees with Hamiltonian square

Published online by Cambridge University Press:  26 February 2010

Frank Harary
Affiliation:
University of Michigan.
Allen Schwenk
Affiliation:
University of Waterloo.
Get access

Extract

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.

MSC classification

Secondary: 05C05: Trees
Type
Research Article
Copyright
Copyright © University College London 1971

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Fleischner, H., “The square of every nonseparable graph is hamiltonian,” to appear.Google Scholar
2.Hararay, F., Graph Theory (Addison-Wesley, Reading, Mass. 1969).CrossRefGoogle Scholar
3.Karaganis, J., “On the cube of a graph,” Canad. Math. Bull., 11 (1968), 295296.CrossRefGoogle Scholar
4.Neumann, F., “On a certain ordering of the vertices of a tree,” Casopis Pest. Mat., 89 (1964), 323339.CrossRefGoogle Scholar