On $2$-steps-Hamiltonian Cubic Graphs

Abstract

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. A $(p,q)$-graph $G=(V,E)$ is said to be AL($k$)-traversal if there exists a sequence of vertices $(v_1,v_2,\dots ,v_p)$ such that for each $i=1,2,\dots ,p-1$, the distance between $v_i$ and $v_{i+1}$ is equal to $k$. We call a graph $G$ a 2-steps Hamiltonian graph if it has an AL(2)-traversal in $G$ and $d(v_p,v_1)=2$. In this paper, we characterize some cubic graphs that are 2-steps Hamiltonian. We show that no forbidden subgraph characterization for non-2-steps-Hamiltonian cubic graphs is available by demonstrating that every cubic graph is a homeomorphic subgraph of a non-2-steps Hamiltonian cubic graph.