A complete solution of 3-step hamiltonian grids and torus graphs

• Published in: Thai Journal of Mathematics
• Main Author: Lau G.-C.; Lee S.-M.; Schaffer K.; Tong S.-M.
• Format: Article
• Language: English
• Published: Chiang Mai University 2019
• Online Access: https://www.scopus.com/inward/record.uri?eid=2-s2.0-85066785559&partnerID=40&md5=71dfc9b7c8aa6daf379c4add328a9826

For a (p; q)-graph G, if the vertices of G can be arranged in a sequence v1; v2;...; vp such that for each i = 1; 2;...; p - 1, the distance from vi to vi+1 equal to k, then the sequence is called an AL(k)-step traversal. Furthermore, if d(vp; v1) = k, the sequence v1; v2;...; vp; v1 is called a k-step Hamiltonian tour and G is k-step Hamiltonian. In this paper we completely determine which rectangular grid graphs are 3-step Hamiltonian and show that the torus graph Cm×Cn is 3-step Hamiltonian for all m ≥ 3; n ≥ 5. © 2019 by the Mathematical Association of Thailand.