Revisiting the Hamiltonian Theme in the Square of a Block: The General Case

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\le i\le 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 \cite[Theorem 2]{cf1:refer} 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.

34 pages