A Note on \(k\)-Step Hamiltonian Graphs
Abd Aziz, N. A., Rad, N. J., Kamarulhaili, H., and Hasni, R.
Corresponding Email: hroslan@umt.edu.my
Received date: 9 January 2018
Accepted date: 24 February 2019
Abstract:
For a given integer \(k\), a given graph \(G\) on \(n\) vertices is called \(k\)-step Hamiltonian (or just \(k\)-SH) if the vertices of \(G\) can be labeled as \(v_1,v_2,...,v_n\) such that \(d(v_1, v_n)=k\) and \(d(v_i, v_{i+1})=k\) for each \(i=1,2,...,n-1\). In this paper, we present a construction namely \(B\)-construction that produces a \((k+i)\)-SH graph from any \(k\)-SH graph \(G\) for every positive integer \(i\geq 1\).
Keywords: Hamiltonian graph, \(k\)-Step Hamiltonian graph