JUCS - Journal of Universal Computer Science 13(11): 1791-1800, doi: 10.3217/jucs-013-11-1791
Hamiltonicity of Topological Grid Graphs
expand article infoChristina Zamfirescu‡, Tudor Zamfirescu§
‡ City University of New York, New York, United States of America§ Universität Dortmund, Dortmund, Germany

Corresponding author: Christina Zamfirescu ( christina.zamfirescu@hunter.cuny.edu )

© Christina Zamfirescu, Tudor Zamfirescu.
This article is freely available under the J.UCS Open Content License.
Citation: Zamfirescu C, Zamfirescu T (2007) Hamiltonicity of Topological Grid Graphs. JUCS - Journal of Universal Computer Science 13(11): 1791-1800. https://doi.org/10.3217/jucs-013-11-1791
Open Access
Abstract
In this paper we study connectivity and hamiltonicity properties of the topological grid graphs, which are a natural type of planar graphs associated with finite subgraphs of the usual square lattice graph of the plane. The main results are as follows. The shortness coefficient of the family of all topological grid graphs is at most 16/17. Every 3-connected topological grid graph is hamiltonian.
Keywords
grid graph, topological grid graph, hamiltonian graph, shortness coefficient, 3-connectedness