Hamiltonicity of Topological Grid Graphs
Дата
Авторы
Zamfirescu,Christina
Zamfirescu,Tudor
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
grid graph , topological grid graph , hamiltonian graph , shortness coefficient , 3-connectedness