Hamiltonian Paths in the Square of a Tree

We introduce a new family of graphs for which the Hamiltonian path problem is non-trivial and yet has a linear time solution. The square of a graph

G

 = (

V

,

E

), denoted as

G

2

, is a graph with the set of vertices

V

, in which two vertices are connected by an edge if there exists a path of length at most 2 connecting them in

G

. Harary & Schwenk (1971) proved that the square of a tree

T

contains a Hamiltonian cycle if and only if

T

is a caterpillar, i.e., it is a single path with several leafs connected to it. Our first main result is a simple graph-theoretic characterization of trees

T

for which

T

2

contains a Hamiltonian path:

T

2

has a Hamiltonian path if and only if

T

is a horsetail (the name is due to the characteristic shape of these trees, see Figure 1). Our next results are two efficient algorithms: linear time testing if

T

2

contains a Hamiltonian path and finding such a path (if there is any), and linear time preprocessing after which we can check for any pair (

u

,

v

) of nodes of

T

in constant time if there is a Hamiltonian path from

u

to

v

in

T

2

.