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

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n1.a7

Authors

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)

Abstract

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.

Keywords

Hamiltonian cycles and paths, square of a block

2010 Mathematics Subject Classification

05C38, 05C45

Received 1 June 2015

Published 5 January 2018