Том 22, номер 2, 2015 г., Стр. 27−48

УДК 519.17
П. А. Иржавский 
Циклические свойства топологических графов шестиугольной решётки

Аннотация:
Исследованы циклические свойства топологических графов шестиугольной решётки. Получено достаточное условие гамильтоновости таких графов. Найден наименьший 2-связный негамильтонов топологический граф шестиугольной решётки. Установлена верхняя оценка коэффициента сжатости изучаемого класса графов.
Ил. 17, библиогр. 18.

Ключевые слова: плоский граф, шестиугольная решётка, гамильтонов цикл, коэффициент сжатости.

DOI: 10.17377/daio.2015.22.440

Иржавский Павел Александрович ¹
1. Белорусский гос. университет
пр. Независимости, 4, 220030 Минск, Беларусь
е-mail: irzhavski@bsu.by

Статья поступила 16 февраля 2014 г.
Исправленный вариант — 5 августа 2014 г.

Литература

[1] Бенедиктович В. И., Сарванов В. И. О гамильтоновости кубических планарных графов // Докл. АН Беларуси. 1997. Т. 41, № 1. C. 34–37.

[2] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384 с.

[3] Пронин Ф. В. Линейный алгоритм построения гамильтонова цикла в локально связном графе треугольной решетки // Вестн. БГУ. Сер. 1. 2011. №1. С. 90–96.

[4] Сарванов В. И. Об одном классе гамильтоновых плоских графов // Докл. АН БССР. 1980. Т. 24, № 9. C. 792–794.

[5] Фляйшнер Г. Эйлеровы графы и смежные вопросы. М.: Мир, 2002. 335 с.

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

[7] Arkin E. M. Not being (super)thin or solid is hard. A study of grid Hamiltonicity // Comput. Geom. 2009. Vol. 42. P. 582–605.

[8] Barnette D. Conjecture 5 // Recent progress in combinatorics. New York: Acad. Press, 1969. P. 343.

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

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

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

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

[13] Karp R. M. Reducibility among combinatorial problems // Complexity of computer computations. IBM Res. Symp. Ser. New York: Plenum Press, 1972. P. 85–103.

[14] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. The traveling salesman problem. A guided tour of combinatorial optimization. Wiley: Chichester, 1985. 465 p.

[15] Read R. C., Wilson R. J. An atlas of graphs. Oxford: Oxford Univ. Press, 1998. 472 p.

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

[17] Umans C., Lenhart W. Hamiltonian cycles in solid grid graphs // Proc. 38th IEEE Symp. Foundations of Computer Science (Miami Beach, FL, USA, October 19–22, 1997). P. 496–507.

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