Journal of Combinatorics

Volume 10 (2019)

Number 1

Revisiting the Hamiltonian theme in the square of a block: the general case

Pages: 163 – 201

DOI: https://dx.doi.org/10.4310/JOC.2019.v10.n1.a7

Authors

Herbert Fleischner (Algorithms and Complexity Group, Institute of Logic and Computation, Technical University of Vienna, Austria)

Gek L. Chia (Dept. of Mathematical and Actuarial Sciences, Faculty of Engineering and Science, Universiti Tunku Abdul Rahman, Sungai Long, Selangor, Malaysia; and Institute of Mathematical Sciences, University of Malaya, Kuala Lumpur, Malaysia)

Abstract

This is the second part of joint research in which we show that every $2$-connected graph $G$ has the $\mathcal{F}_4$ property. That is, given distinct $x_i \in V (G), 1 \leq i \leq 4$, there is an $x_1 x_2$-hamiltonian path in $G^2$ containing different edges $x_3 y_3, x_4 y_4 \in E(G)$ for some $y_3, y_4 \in V(G)$. However, it was shown already in [3], Theorem 2, that $2$-connected DT-graphs have the $\mathcal{F}_4$ property; based on this result we generalize it to arbitrary $2$-connected graphs.We also show that these results are best possible.

Keywords

Hamiltonian cycles and paths, square of a block

2010 Mathematics Subject Classification

05C38, 05C45

Received 30 September 2015

Published 7 December 2018