A Note Concerning Hamilton Cycles in Some Classes of Grid Graphs
| Main Authors: | Salman, A. N.M.; Faculty of Mathematical Sciences, University of Twente P.O. Box 217, 7500 AE Enschede, The Netherlands, Baskoro, E. T.; The Department of Mathematics, ITB Jalan Ganesa 10 Bandung 40132, Indonesia, Broersma, H. J.; Faculty of Mathematical Sciences, University of Twente P.O. Box 217, 7500 AE Enschede, The Netherlands |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
ITB Journal Publisher, LPPM ITB
, 2013
|
| Subjects: | |
| Online Access: |
http://journals.itb.ac.id/index.php/jmfs/article/view/257 http://journals.itb.ac.id/index.php/jmfs/article/view/257/239 |
Daftar Isi:
- 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.