A Note Concerning Hamilton Cycles in Some Classes of Grid Graphs

A. N.M. Salman, E. T. Baskoro, H. J. Broersma

Abstract


A graph G is called hamiltonian if it contains a Hamilton cycle, i.e. a cycle containing all vertices. Deciding whether a given graph has a Hamilton cycle is an NP-complete problem. But, it is a polynomial problem within some special graph classes. In this paper we consider three classes of grid graphs, namely rectangular grid graph, eta grid graph and omega grid graph. Our main result characterizes which of these graphs are hamiltonian.


Full Text:

PDF


DOI: http://dx.doi.org/10.5614%2Fitbj.sci.2003.35.1.5

Refbacks

  • There are currently no refbacks.


View my Stats

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.