On \(k\)-step Hamiltonian graphs (Q2927768)

A simple graph is said to admit an AL(\(k\))-traversal if there exists a sequence of vertices such that the distance between two adjacent vertices in the sequence is equal to \(k\). A graph is \(k\)-step Hamiltonian if it has an AL(\(k\))-traversal and the distance between the first and last vertex in the sequence is equal to \(k\). This paper considers graphs that are \(k\)-step Hamiltonian. The authors show that all bipartite graphs are not \(k\)-step Hamiltonian for even integer \(k\). Any graph is shown to be an induced subgraph of a \(k\)-step Hamiltonian graph.