Volume 22, No 2, 2015, P. 27-48

UDC 519.17
P. A. Irzhavski
Cyclic properties of topological graphs of a hexagonal grid

Abstract:
We study cyclic properties of topological graphs of a hexagonal grid. A sufficient condition for Hamiltonicity of such graphs is obtained. We find the smallest 2-connected non-Hamiltonian topological graph of a hexagonal grid. An upper bound for the shortness coefficient of this class of graphs is established.
Ill. 17, bibliogr. 18.

Keywords: plane graph, hexagonal grid, Hamilton cycle, shortness coefficient.

DOI: 10.17377/daio.2015.22.440

Pavel A. Irzhavski ¹
1. Belarusian State University,
4 Nezavisimosti Ave., 220030 Minsk, Belarus
 е-mail: irzhavski@bsu.by

Received 16 February 2014
Revised 5 August 2014

References

[1] V. I. Benediktovich and V. I. Sarvanov, On Hamiltonicity of cubic planar graphs, Dokl. Akad. Nauk Belarusi, 41, No. 1, 34–37, 1997.

[2] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lektsii po teorii grafov, Nauka, Moscow, 1990. Translated under the title Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994.

[3] F. V. Pronin, A linear algorithm for constructing a Hamiltonian cycle in a locally connected graph of a triangular lattice, Vestn. Beloruss. Gos. Univ., Ser. 1, No. 1, 90–96, 2011.

[4] V. I. Sarvanov, On a class of Hamiltonian planar graphs, Dokl. Akad. Nauk BSSR, 24, No. 9, 792–794, 1980.

[5] H. Fleischner, Eulerian Graphs and Related Topics, Part 1, Vol. 1, North-Holland, Amsterdam, 1990 (Ann. Discrete Math., Vol. 45). Translated under the title Eilerovy grafy i smezhnye voprosy, Mir, Moscow, 2002.

[6] T. Akiyama, T. Nishizeki, and N. Saito, NP-completeness of the Hamiltonian cycle problem for bipartite graphs, J. Inf. Process., 3, 73–76, 1980.

[7] E. M. Arkin, S. P. Fekete, K. Islam [et al.], Not being (super)thin or solid is hard: A study of grid Hamiltonicity, Comput. Geom., 42, No. 6–7, 582–605, 2009.

[8] D. Barnette, Conjecture 5, in W. T. Tutte, ed., Recent Progress in Combinatorics (Proc. 3rd Waterloo Conf. Combinatorics, May 1968), p. 343, Acad. Press, New York, 1969.

[9] M. R. Garey, D. S. Johnson, and R. E. Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput., 5, 704–714, 1976.

[10] V. S. Gordon, Yu. L. Orlovich, and F. Werner, Hamiltonian properties of triangular grid graphs, Discrete Math., 308, 6166–6188, 2008.

[11] B. Grünbaum and H. Walther, Shortness exponents of families of graphs, J. Comb. Theory, Ser. A, 14, 364–385, 1973.

[12] A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter, Hamilton paths in grid graphs, SIAM J. Comput., 11, 676–686, 1982.

[13] R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher, eds., Complexity of Computer Computations (Proc. Symp. Complex. Comput. Comput., New York, USA, Mar. 20–22, 1972), pp. 85–103, Plenum Press, New York, 1972 (IBM Res. Symp. Ser.).

[14] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, New York, 1985.

[15] R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford Univ. Press, Oxford, England, 1998.

[16] R. Thomas and X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Comb. Theory, Ser. B, 62, 114–132, 1994.

[17] C. Umans and W. Lenhart, Hamiltonian cycles in solid grid graphs, in Proc. 38th IEEE Symp. Foundations Comput. Sci., Miami Beach, FL, USA, Oct. 20–22, 1997, pp. 496–507, IEEE Comput. Soc., Los Alamitos, USA, 1997.

[18] C. Zamfirescu and T. Zamfirescu, Hamiltonicity of topological grid graphs, J. UCS, 13, No. 11, 1791–1800, 2007.