Journal of Combinatorics

Volume 9 (2018)

Number 1

Revisiting the Hamiltonian theme in the square of a block: the case of $DT$-graphs

Pages: 119 – 161



Gek L. Chia (Department of Mathematical and Actuarial Sciences, Universiti Tunku Abdul Rahman, Cheras, Kajang, Selangor, Malaysia; and Institute of Mathematical Sciences, University of Malaya, Kuala Lumpur, Malaysia)

Jan Ekstein (Department of Mathematics, Institute for Theoretical Computer Science, University of West Bohemia, Plzeň, Czech Republic)

Herbert Fleischner (Institut für Computergraphik und Algorithmen, Technical University of Vienna, Austria)


The square of a graph $G$, denoted $G^2$, is the graph obtained from $G$ by joining by an edge any two nonadjacent vertices which have a common neighbor. A graph $G$ is said to have the $\mathcal{F}_k$ property if for any set of $k$ distinct vertices $\lbrace x_1, x_2, \dotsc , x_k \rbrace$ in $G$, there is a Hamiltonian path from $x_1$ to $x_2$ in $G^2$ containing $k-2$ distinct edges of $G$ of the form $x_i z_i , i = 3 , \dotsc , k$. In [7], it was proved that every $2$-connected graph has the $\mathcal{F}_3$ property. In the first part of this work, we extend this result by proving that every $2$-connected $DT$-graph has the $\mathcal{F}_3$ property (Theorem 2) and will show in the second part that this generalization holds for arbitrary $2$-connected graphs, and that there exist $2$-connected graphs which do not have the $\mathcal{F}_k$ property for any natural number $k \geq 5$. Altogether, this answers the second problem raised in [4] in the affirmative.


Hamiltonian cycles and paths, square of a block

2010 Mathematics Subject Classification

05C38, 05C45

The first author was supported by the FRGS Grant (FP036-2013B).

The second author was supported by P202/12/G061 of the Grant Agency of the Czech Republic.

The third author was supported by FWF-grant P27615-N25.

Received 1 June 2015

Published 5 January 2018