On $k$-step Hamiltonian Graphs

Abstract

For integers $k\ge 1$, a $(p,q)$-graph $G=(V,E)$ is said to admit an 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 $k$. We call a graph $k$-step Hamiltonian (or say it admits a $k$-step Hamiltonian tour) if it has an AL($k$)-traversal and $d(v_1,v_p)=k$. In this paper, we investigate the $k$-step Hamiltonicity of graphs. In particular, we show that every graph is an induced subgraph of a $k$-step Hamiltonian graph for all $k\ge 2$.