05988633

a

05988633 Radoszewski, Jakub Rytter, Wojciech Hamiltonian paths in the square of a tree. Asano, Takao (ed.) et al., Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5--8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25590-8/pbk). Lecture Notes in Computer Science 7074, 90-99 (2011). 2011 Berlin: Springer EN tree square of a graph Hamiltonian path

doi:10.1007/978-3-642-25591-5_11

Summary: 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}$.