2-nearly Platonic graphs

Jendrol', Stanislav 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 351-362

Résumé

A 2-nearly Platonic graph of type (k, d) is a k-regular plane graph with f faces, f - 2 of which are of size d and the remaining two are of sizes d_1, d_2, both different from d. Such a graph is called balanced if d_1 = d_2. We show that all connected 2-nearly Platonic graphs are balanced. This proves a recent conjecture by Keith, Froncek, and Kreher. We also show that any 2-nearly Platonic graph belongs to one of 15 well defined infinite classes. The latter states more precisely the statement of Deza, Dutour Sikirič, and Shtogrin from 2013, and of Froncek, Khorsandi, Musawi, and Qui from 2021 that there are only 14 such classes. Moreover, our short proof provides a complete characterization of all 2-nearly Platonic graphs.

Détail

Keywords: plane graph, Platonic solid, almost Platonic graph

Bibliographie

[1] P.R. Cromwell, Polyhedra (Cambridge University Press, 1997).

[2] D.W. Crowe, Nearly regular polyhedra with two exceptional faces, in: The Many Facets of Graph Theory, Proc. Conf. Western Mich. Univ., Kalamazoo, MI, 1968, (Springer, Berlin 1969) 63–76.

[3] M. Deza and M. Dutour Sikirić, Geometry of Chemical Graphs: Polycycles and Two-faced Maps (Cambridge University Press, 2008). https://doi.org/10.1017/CBO9780511721311

[4] M. Deza, M. Dutour Sikirić and M. Shtogrin, Fullerene-like spheres with faces of negative curvature, in: Diamond and Related Nanostructures, Chapter 13, M.V. Diudea and C.L. Nagy (Ed(s)), (Springer 2013). https://doi.org/10.1007/978-94-007-6371-5_13

[5] R. Diestel, Graph Theory (Springer-Verlag, Berlin, Heidelberg, 2005). https://doi.org/10.1007/978-3-662-53622-3

[6] D. Froncek and J. Qiu, Balanced 3-nearly Platonic graphs, Bull. Inst. Combin. Appl. 86 (2019) 34–63.

[7] D. Froncek, M.R. Khorsadi, S.R. Musawi and J. Qiu, {A note on nearly Platonic graphs with connectivity one}, Electron. J. Graph Theory Appl. (EJGTA) 9 (2021) 195–205. https://doi.org/10.5614/ejgta.2021.9.1.17

[8] D. Froncek, M.R. Khorsadi, S.R. Musawi and J. Qiu, 2-nearly Platonic graphs are unique, manuscript, March 2021.

[9] B. Grünbaum, Convex Polytopes, in: Grad. Texts in Math. 221 (Springer-Verlag, New York, 2003). https://doi.org/10.1007/978-1-4613-0019-9

[10] M. Horňák, A theorem on nonexistence of a certain type of nearly regular cell-decomposition of the sphere, Časopis Pěst. Mat. 103 (1978) 333–338. https://doi.org/10.21136/CPM.1978.117991

[11] M. Horňák and E. Jucovič, Nearly regular-cell decomposition of orientable 2-manifold with at most two exceptional cells, Math. Slovaca 27 (1977) 73–89.

[12] S. Jendroľ, On the non-existence of certain nearly regular planar maps with two exceptional faces, Mat. Čas. 25 (1975) 159–164.

[13] S. Jendroľ, On the face-vectors of trivalent convex polyhedra, Math. Slovaca 33 (1983) 165–180.

[14] S. Jendroľ, On face-vectors of 5-valent convex 3-polytopes, J. Geom. 50 (1994) 100–110. https://doi.org/10.1007/BF01222667

[15] S. Jendroľ \ and R. Soták, On the cyclic coloring conjecture, Discrete Math. 344 (2021) 112204. https://doi.org/10.1016/j.disc.2020.112204

[16] E. Jucovič, On the face-vector of a 4-valent 3-polytope, Studia Sci. Math. Hungar. 72 (1973) 53–57.

[17] W. Keith, D. Froncek and D. Kreher, A note on nearly Platonic graphs, Australas. J. Combin. 70 (2018) 86–103.

[18] W. Keith, D. Froncek and D. Kreher, Corrigendum to: A note on nearly Platonic graphs, Australas. J. Combin. 72 (2018) 163.

[19] J. Malkevitch, Properties of Planar Graphs with Uniform Vertex and Face Structure, in: Men. Amer. Math. Soc. 99 (American Mathematical Society, Providence, R.I., 1970). https://doi.org/10.1090/memo/0099

[20] E. Schulte, Chiral polyhedra in oridinary space I}, Discrete Comput. Geom. 32 (2004) 55–99. https://doi.org/10.1007/s00454-004-0843-x