Contents Online

# 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: http://dx.doi.org/10.4310/JOC.2018.v9.n1.a7

#### Authors

#### 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

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