Hamiltonian walks and Hamiltonian-connected 3-path graphs

Abstract

A Hamiltonian walk in a nontrivial connected graph $G$ is a closed walk of minimum length that contains every vertex of $G$. The 3-path graph $P_3(G)$ of a connected graph $G$ of order 3 or more has the set of all 3-paths (paths of order 3) of $G$ as its vertex set and two vertices of $P_3(G)$ are adjacent if they have a 2-path in common. With the aid of Hamiltonian walks in spanning trees of the 3-path graph of a graph, it is shown that if $G$ is a connected graph with minimum degree at least 4, then $P_3(G)$ is Hamiltonian-connected.