×

zbMATH — the first resource for mathematics

Cycles in 5-connected triangulations. (English) Zbl 1430.05018
Summary: We show that in 5-connected planar and projective planar triangulations on \(n\) vertices, the number of Hamiltonian cycles grows exponentially with \(n\). The result is best possible in the sense that 4-connected triangulations on \(n\) vertices on any fixed surface may have only polynomially many cycles. Also, there is an infinite class of 5-connected graphs (not on a fixed surface) which have only polynomially many cycles. The result also extends to 5-connected triangulations of the torus if a long standing conjecture of Nash-Williams holds [C. St. J. A. Nash-Williams, in: New directions in the theory of graphs. Proceedings of the third Ann Arbor conference on graph theory, University of Michigan, October 21–23, 1971. New York-London: Academic Press. 149–186 (1973; Zbl 0263.05101)]. For any fixed surface, we show that every 5-connected triangulation of large face-width on that surface contains exponentially many cycles.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alahmadi, A.; Aldred, R. E.L.; dela Cruz, R.; Solé, P.; Thomassen, C., The maximum number of minimal codewords in long codes, Discrete Appl. Math., 161, 424-429 (2013) · Zbl 1254.05084
[2] Alahmadi, A.; Aldred, R. E.L.; dela Cruz, R.; Solé, P.; Thomassen, C., The maximum number of minimal codewords in an [n,k]-code, Discrete Math., 313, 1569-1574 (2013) · Zbl 1281.94099
[3] Alahmadi, A.; Aldred, R. E.L.; dela Cruz, R.; Ok, S.; Solé, P.; Thomassen, C., The minimum number of minimal codewords in an [n,k]-code and in graphic codes, Discrete Appl. Math., 184, 32-39 (2015) · Zbl 1311.05027
[4] Aldred, R. E.L.; Thomassen, C., On the number of cycles in 3-connected cubic graphs, J. Combin. Theory Ser. B, 71, 79-84 (1997) · Zbl 0918.05068
[5] Barefoot, C. A.; Clark, L.; Entringer, R. C., Cubic graphs with the minimum number of cycles, Congr. Numer., 53, 49-62 (1986) · Zbl 0623.05033
[6] Böhme, T.; Harant, J.; Tkáč, M., On certain Hamiltonian cycles in planar graphs, J. Graph Theory, 32, 81-96 (1999) · Zbl 0931.05047
[7] Böhme, T.; Mohar, B.; Thomassen, C., Long cycles in graphs on a fixed surface, J. Combin. Theory Ser. B, 85, 338-347 (2002) · Zbl 1025.05035
[8] Hakimi, S. L.; Schmeichel, E. F.; Thomassen, C., On the number of Hamiltonian cycles in a maximal planar graph, J. Graph Theory, 3, 365-370 (1979) · Zbl 0422.05050
[9] Mohar, B.; Thomassen, C., Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences (2001), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD, xii+291 pp · Zbl 0979.05002
[10] Nash-Williams, C. St. J.A., Unexplored and semi-explored territories in graph theory, (New Directions in Graph Theory (1973), Academic Press: Academic Press New York), 169-176 · Zbl 0263.05101
[11] Thomas, R.; Yu, X., 4-Connected projective planar graphs are Hamiltonian, J. Combin. Theory Ser. B, 62, 114-132 (1994) · Zbl 0802.05051
[12] Thomassen, C., A theorem on paths in planar graphs, J. Graph Theory, 7, 165-169 (1983) · Zbl 0515.05040
[13] Tutte, W. T., A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116 (1956) · Zbl 0070.18403
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.