×

The set of vertices with positive curvature in a planar graph with nonnegative curvature. (English) Zbl 1403.05034

Summary: In this paper, we give the sharp upper bound for the number of vertices with positive curvature in a planar graph with nonnegative combinatorial curvature. Based on this, we show that the automorphism group of a planar – possibly infinite – graph with nonnegative combinatorial curvature and positive total curvature is a finite group, and give an upper bound estimate for the order of the group.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
31C05 Harmonic, subharmonic, superharmonic functions on other spaces
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Appel, K.; Haken, W., Every planar map is four colorable. I. Discharging, Illinois J. Math., 21, 3, 429-490 (1977) · Zbl 0387.05009
[2] Alexandrov, A. D., Convex Polyhedra, Springer Monographs in Mathematics (2005), Springer-Verlag: Springer-Verlag Berlin, translated from the 1950 Russian edition by N.S. Dairbekov, S.S. Kutateladze and A.B. Sossinsky, with comments and bibliography by V.A. Zalgaller and appendices by L.A. Shor and Yu.A. Volkov · Zbl 1067.52011
[3] Babai, L., Automorphism groups of planar graphs. II, Colloq. Math. Soc. János Bolyai, 10, 29-84 (1975) · Zbl 0301.05116
[4] Burago, D.; Burago, Yu.; Ivanov, S., A Course in Metric Geometry, Graduate Studies in Mathematics, vol. 33 (2001), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0981.51016
[5] Brinkmann, G.; Dress, A. W.M., A constructive enumeration of fullerenes, J. Algorithms, 23, 2, 345-358 (1997)
[6] Buchstaber, V.; Erokhovets, N., Finite sets of operations sufficient to construct any fullerene from \(C_{20}\), Struct. Chem., 28, 1, 225-234 (2017)
[7] Buchstaber, V. M.; Erokhovets, N. Yu., Constructions of families of three-dimensional polytopes, characteristic patches of fullerenes, and Pogorelov polytopes, Izv. Ross. Akad. Nauk Ser. Mat., 81, 5, 15-91 (2017) · Zbl 1378.05196
[8] Brinkmann, G.; Goedgebeur, J.; McKay, B. D., The generation of fullerenes, J. Chem. Inf. Model., 52, 11, 2910-2918 (2012)
[9] Baues, O.; Peyerimhoff, N., Curvature and geometry of tessellating plane graphs, Discrete Comput. Geom., 25, 1, 141-159 (2001) · Zbl 0963.05031
[10] Baues, O.; Peyerimhoff, N., Geodesics in non-positively curved plane tessellations, Adv. Geom., 6, 2, 243-263 (2006) · Zbl 1098.53034
[11] Conway, J. H.; Burgiel, H.; Goodman-Strauss, C., The Symmetries of Things (2008), A K Peters, Ltd.: A K Peters, Ltd. Wellesley, MA · Zbl 1173.00001
[12] Chen, B.; Chen, G., Gauss-Bonnet formula, finiteness condition, and characterizations of graphs embedded in surfaces, Graphs Combin., 24, 3, 159-183 (2008) · Zbl 1170.05011
[13] Chen, B., The Gauss-Bonnet formula of polytopal manifolds and the characterization of embedded graphs with nonnegative curvature, Proc. Amer. Math. Soc., 137, 5, 1601-1611 (2009) · Zbl 1180.05037
[14] DeVos, M.; Mohar, B., An analogue of the Descartes-Euler formula for infinite graphs and Higuchi’s conjecture, Trans. Amer. Math. Soc., 359, 7, 3287-3300 (2007) · Zbl 1117.05026
[15] Galebach, B., \(n\)-Uniform tilings (2009), available online at
[16] Ghidelli, L., On the largest planar graphs with everywhere positive combinatorial curvature (2017) · Zbl 1502.05041
[17] Gromov, M., Hyperbolic groups, (Essays in Group Theory. Essays in Group Theory, Math. Sci. Res. Inst. Publ., vol. 8 (1987), Springer: Springer New York), 75-263 · Zbl 0634.20015
[18] Grünbaum, B.; Shephard, G. C., Tilings and Patterns, A Series of Books in the Mathematical Sciences (1989), W. H. Freeman and Company: W. H. Freeman and Company New York · Zbl 0601.05001
[19] Higuchi, Y., Combinatorial curvature for planar graphs, J. Graph Theory, 38, 4, 220-229 (2001) · Zbl 0996.05041
[20] Häggström, O.; Jonasson, J.; Lyons, R., Explicit isoperimetric constants and phase transitions in the random-cluster model, Ann. Probab., 30, 1, 443-473 (2002) · Zbl 1025.60044
[21] Hua, B.; Jost, J.; Liu, S., Geometric analysis aspects of infinite semiplanar graphs with nonnegative curvature, J. Reine Angew. Math., 700, 1-36 (2015) · Zbl 1308.05033
[22] Hua, B.; Lin, Y., Curvature notions on graphs, Front. Math. China, 11, 5, 1275-1290 (2016) · Zbl 1352.31004
[23] Higuchi, Y.; Shirai, T., Isoperimetric constants of \((d, f)\)-regular planar graphs, Interdiscip. Inform. Sci., 9, 2, 221-228 (2003) · Zbl 1048.05030
[24] Hua, B.; Su, Y., Total curvature of planar graphs with nonnegative curvature (2017)
[25] Imrich, W., On Whitney’s theorem on the unique embeddability of 3-connected planar graphs, (Recent Advances in Graph Theory (1975)), 303-306, (loose errata)
[26] Ishida, M., Pseudo-curvature of a graph, (Lecture at Workshop on Topological Graph Theory (1990), Yokohama National University)
[27] Keller, M., The essential spectrum of the Laplacian on rapidly branching tessellations, Math. Ann., 346, 1, 51-66 (2010) · Zbl 1285.05115
[28] Keller, M., Curvature, geometry and spectral properties of planar graphs, Discrete Comput. Geom., 46, 3, 500-525 (2011) · Zbl 1228.05129
[29] Kroto, H. W.; Heath, J. R.; O’Brien, S. C.; Curl, R. F.; Smalley, R. E., Nature, 318, 162-163 (1985), \(C_{60}\): buckminsterfullerene
[30] Keller, M.; Peyerimhoff, N., Cheeger constants, growth and spectrum of locally tessellating planar graphs, Math. Z., 268, 3-4, 871-886 (2011) · Zbl 1250.05039
[31] Lawrencenko, S.; Plummer, M. D.; Zha, X., Isoperimetric constants of infinite plane graphs, Discrete Comput. Geom., 28, 3, 313-330 (2002) · Zbl 1001.05066
[32] Mani, P., Automorphismen von polyedrischen Graphen, Math. Ann., 192, 279-303 (1971) · Zbl 0206.51402
[33] Mohar, B., Embeddings of infinite graphs, J. Combin. Theory Ser. B, 44, 1, 29-43 (1988) · Zbl 0591.05028
[34] Mohar, B., Light structures in infinite planar graphs without the strong isoperimetric property, Trans. Amer. Math. Soc., 354, 8, 3059-3074 (2002) · Zbl 0996.05031
[35] Nevanlinna, R., Analytic Functions, Die Grundlehren der mathematischen Wissenschaften, vol. 162 (1970), Springer-Verlag: Springer-Verlag New York-Berlin, translated from the second German edition by Phillip Emig · JFM 62.0315.02
[36] Nicholson, R.; Sneddon, J., New graphs with thinly spread positive combinatorial curvature, New Zealand J. Math., 41, 39-43 (2011) · Zbl 1235.05039
[37] Oh, B.-G., On the number of vertices of positively curved planar graphs, Discrete Math., 340, 6, 1300-1310 (2017) · Zbl 1369.05051
[38] Oldridge, P. R., Characterizing the polyhedral graphs with positive combinatorial curvature (2017), thesis, available at
[39] Réti, T.; Bitay, E.; Kosztolányi, Z., On the polyhedral graphs with positive combinatorial curvature, Acta Polytech. Hung., 2, 2, 19-37 (2005)
[40] Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R., The four-colour theorem, J. Combin. Theory Ser. B, 70, 1, 2-44 (1997) · Zbl 0883.05056
[41] Servatius, B.; Servatius, H., Symmetry, automorphisms, and self-duality of infinite planar graphs and tilings, (International Scientific Conference on Mathematics. Proceedings. International Scientific Conference on Mathematics. Proceedings, Žilina, 1998 (1998), Univ. Žilina: Univ. Žilina Žilina), 83-116 · Zbl 0992.52005
[42] Stone, D. A., A combinatorial analogue of a theorem of Myers, Illinois J. Math., 20, 1, 12-21 (1976) · Zbl 0316.57001
[43] Sun, L.; Yu, X., Positively curved cubic plane graphs are finite, J. Graph Theory, 47, 4, 241-274 (2004) · Zbl 1055.05038
[44] Thomassen, C., Duality of infinite graphs, J. Combin. Theory Ser. B, 33, 2, 137-160 (1982) · Zbl 0501.05054
[45] Thurston, W. P., Shapes of polyhedra and triangulations of the sphere, (The Epstein Birthday Schrift. The Epstein Birthday Schrift, Geom. Topol. Monogr., vol. 1 (1998), Geom. Topol. Publ.: Geom. Topol. Publ. Coventry), 511-549 · Zbl 0931.57010
[46] Whitney, H., 2-isomorphic graphs, Amer. J. Math., 55, 1-4, 245-254 (1933) · JFM 59.1235.01
[47] Woess, W., A note on tilings and strong isoperimetric inequality, Math. Proc. Cambridge Philos. Soc., 124, 385-393 (1998) · Zbl 0914.05015
[48] Żuk, A., On the norms of the random walks on planar graphs, Ann. Inst. Fourier (Grenoble), 47, 5, 1463-1490 (1997) · Zbl 0897.60079
[49] Zhang, L., A result on combinatorial curvature for embedded graphs on a surface, Discrete Math., 308, 24, 6588-6595 (2008) · Zbl 1161.05031
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.