Geodesic
Cyclic properties of topological graphs of a~hexagonal grid
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 2, pp. 27-48.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, Hamilton cycle, shortness coefficient.
Mots-clés : hexagonal grid 
@article{DA_2015_22_2_a2,
     author = {P. A. Irzhavski},
     title = {Cyclic properties of topological graphs of a~hexagonal grid},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {27--48},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_2_a2/}
}
TY  - JOUR
AU  - P. A. Irzhavski
TI  - Cyclic properties of topological graphs of a~hexagonal grid
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 27
EP  - 48
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_2_a2/
LA  - ru
ID  - DA_2015_22_2_a2
ER  - 
%0 Journal Article
%A P. A. Irzhavski
%T Cyclic properties of topological graphs of a~hexagonal grid
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 27-48
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_2_a2/
%G ru
%F DA_2015_22_2_a2
P. A. Irzhavski. Cyclic properties of topological graphs of a~hexagonal grid. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 2, pp. 27-48. http://geodesic.mathdoc.fr/item/DA_2015_22_2_a2/

[1] V. I. Benediktovich, V. I. Sarvanov, “On Hamiltonicity of cubic planar graphs”, Dokl. Akad. Nauk Belarusi, 41:1 (1997), 34–37 | MR | Zbl

[2] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994, 371 pp. | MR | MR

[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, 2011, no. 1, 90–96 | MR | Zbl

[4] V. I. Sarvanov, “On a class of Hamiltonian planar graphs”, Dokl. Akad. Nauk BSSR, 24:9 (1980), 792–794 | MR | Zbl

[5] Fleischner H., Eulerian Graphs and Related Topics, Part 1, v. 1, Ann. Discrete Math., 45, North-Holland, Amsterdam, 1990 | MR | Zbl

[6] Akiyama T., Nishizeki T., Saito N., “NP-completeness of the Hamiltonian cycle problem for bipartite graphs”, J. Inf. Process, 3 (1980), 73–76 | MR | Zbl

[7] Arkin E. M., “Not being (super)thin or solid is hard. A study of grid Hamiltonicity”, Comput. Geom., 42 (2009), 582–605 | DOI | MR | Zbl

[8] Barnette D., “Conjecture 5”, Recent progress in combinatorics, Proc. 3rd Waterloo Conf. Combinatorics (May, 1968), ed. W. T. Tutte, Acad. Press, New York, 1969, 343 | MR

[9] Garey M. R., Johnson D. S., Tarjan R. E., “The planar Hamiltonian circuit problem is NP-complete”, SIAM J. Comput., 5 (1976), 704–714 | DOI | MR | Zbl

[10] Gordon V. S., Orlovich Y. L., Werner F., “Hamiltonian properties of triangular grid graphs”, Discrete Math., 308 (2008), 6166–6188 | DOI | MR | Zbl

[11] Grünbaum B., Walther H., “Shortness exponents of families of graphs”, J. Comb. Theory. Ser. A, 14 (1973), 364–385 | DOI | MR | Zbl

[12] Itai A., Papadimitriou C. H., Szwarcfiter J. L., “Hamilton paths in grid graphs”, SIAM J. Comput., 11 (1982), 676–686 | DOI | MR | Zbl

[13] Karp R. M., “Reducibility among combinatorial problems”, Complexity of computer computations, Proc. Symp. Complex. Comput. Comput. (New York, USA, Mar. 20–22, 1972), IBM Res. Symp. Ser., eds. R. E. Miller, J. W. Thatcher, Plenum Press, New York, 1972, 85–103 | MR

[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 pp. | MR | Zbl

[15] Read R. C., Wilson R. J., An atlas of graphs, Oxford Univ. Press, Oxford, 1998, 472 pp. | MR | Zbl

[16] Thomas R., Yu X., “4-Connected projective-planar graphs are Hamiltonian”, J. Comb. Theory. Ser. B, 62 (1994), 114–132 | DOI | MR | Zbl

[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), IEEE Comput. Soc., Los Alamitos, USA, 1997, 496–507 | DOI

[18] Zamfirescu C., Zamfirescu T., “Hamiltonicity of topological grid graphs”, J. UCS, 13:11 (2007), 1791–1800 | MR