Spanning Trees and Hamiltonicity

Abstract

The 3-path $P_3(G)$ of a connected graph $G$ of order 3 or more has the set of all 3-path (path of order 3) of $G$ as its vertex of $P_3(G)$ are adjacent if they have a 2-path in common. A Hamiltonian walk in a nontrivial connected graph $G$ is a closed walk of minimum length that contains every vertex of $G$. With the aid of spanning trees and Hamiltonian walks in graphs, we provide sufficient conditions for the 3-path graph of a connected graph to be Hamiltonian.