On k-step Hamiltonian Bipartite and Tripartite Graphs

Abstract

For integer $k \geq 1$, a $(p, q)$-graph $G=(V, E)$ is said to admit an $A L(k)$-traversal if there exist a sequence of vertices $\left(v_1, v_2, \ldots, v_p\right)$ such that for each $i=1,2, \ldots, p-1$, the distance between $v_i$ and $v_{i+1}$ is $k$. We call a graph $k$-step Hamiltonian (or admits a $k$-step Hamiltonian tour) if it admits an $A L(k)$-traversal and $d\left(v_1, v_p\right)=$ $k$. In this paper we consider k-step Hamiltonicity of bipartite and tripartite graphs. As an application, we found that a 2-step Hamiltonian tour of a graph could sometimes induce a super-edge-magic labeling of the graph.