The 2-steps Hamiltonian Subdivision Graphs of Cycles with a Chord

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 $k$-steps Hamiltonian graph if it has an $AL(k)$-traversal in $G$ and the distance between $v_p$ and $v_1$ is $k$. In this paper, we completely classify whether a subdivision graph of a cycle with a chord is $2$-steps Hamiltonian.