A Complete Solution of 3-Hamiltonian Grids and Torus Graphs

Gee-Choon Lau, Sin-Min Lee, Karl Schaffer, Siu-Ming Tong

Abstract


For a $(p, q)$-graph $G$, if the vertices of $G$ can be arranged in a sequence $v_1, v_2, \ldots, v_p$ such that for each $i = 1, 2, \ldots, p-1$, the distance from $v_i$ to $v_{i+1}$ equal to $k$, then the sequence is called an $AL(k)$-step traversal. Furthermore, if $d(v_p,v_1) = k$, the sequence $v_1, v_2, \ldots, v_p, v_1$ 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 $C_m \times C_n$ is 3-step Hamiltonian for all $m \ge 3, n \ge 5$.


Full Text: PDF

Refbacks

  • There are currently no refbacks.


The Thai Journal of Mathematics organized and supported by The Mathematical Association of Thailand and Thailand Research Council and the Center for Promotion of Mathematical Research of Thailand (CEPMART).

Copyright 2021 by the Mathematical Association of Thailand.

All rights reserve. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission of the Mathematical Association of Thailand.

|ISSN 1686-0209|