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.