A Note on k-Step Hamiltonian Graphs

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(i), v(i+1)) = 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 >= 1.