Menu
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, \ldots, v_p)\) such that for each \( i = 1, 2, \ldots, 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.