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.