Description of faces in 3-polytopes without vertices of degree from 4 to 9

  • Ivanova Anna O., shmgnanna@mail.ru M. K. Ammosov North-Eastern Federal University, Kulakovskogo st., 48, Yakutsk 677000, Yakutia, Russia
Keywords: planar graph, plane map, structure properties, 3-polytope, weight

Abstract

In 1940, Lebesgue proved that every normal plane map contains a face for which the set of degrees of its vertices is majorized by one of the following sequences: (3, 6,$\infty$), (3, 7, 41), (3, 8, 23), (3, 9, 17), (3, 10, 14), (3, 11, 13), (4, 4, $\infty$), (4, 5, 19), (4, 6, 11), (4, 7, 9), (5, 5, 9), (5, 6, 7), (3, 3, 3, $\infty$), (3, 3, 4, 11), (3, 3, 5, 7), (3, 4, 4, 5), (3, 3, 3, 3, 5). In this note prove that every 3-polytope without vertices of degree from 4 to 9 contains a face for which the set of degrees of its vertices is majorized by one of the following sequences: (3, 3, $\infty$), (3, 10, 12), (3, 3, 3, $\infty$), (3, 3, 3, 3, 3), which is tight.

References

[1]Lebesgue H., “Quelques conséquences simples de la formule d'Euler”, J. Math. Pures Appl., 19 (1940), 27–43  mathscinet
[2]Borodin O. V., “Colorings of plane graphs: a survey”, Discrete Math ., 313:4 (2013), 517–539  crossref  mathscinet  zmath  scopus
[3]Ore O., Plummer M. D., “Cyclic coloration of plane graphs”, Recent progress in combinatorics, ed. W. T. Tutte, Acad. Press, New York, 1969, 287–293  mathscinet
[4]Plummer M. D., Toft B., “Cyclic coloration of 3-polytopes”, J. Graph Theory, 11 (1987), 507–515  crossref  mathscinet  zmath  scopus
[5]Kotzig A., “From the theory of Eulerian polyhedra (Russian)”, Mat. Cas, 13 (1963), 20–31  mathscinet
[6]Borodin O. V., “Solution of Kotzig’s and Grünbaum’s problems on the separability of a cycle in a planar graph”, Mat. Zametki, 46:5 (1989), 9–12  mathnet  mathscinet
[7]Grünbaum B., “Polytopal graphs”, Studies in graph theory, MAA Stud. Math., 12, ed. D. R. Fulkerson, 1975, 201–224  mathscinet  zmath
[8]Plummer M. D., “On the cyclic connectivity of planar graph”, Graph theory and application, Springer-Verl., Berlin, 1972, 235–242  crossref  mathscinet
[9]Steinitz E., “Polyeder und Raumeinteilungen”, Geometrie, v. 3AB, Enzykl. Math. Wiss., 12, 1922, 1–139
[10]Kotzig A., “Extremal polyhedral graphs”, Ann. New York Acad. Sci, 319. (1979), 569–570
[11]Borodin O. V., “Minimal weight of face in plane triangulations without 4-vertices”, Mat. Zametki, 51:1 (1992), 16–19  mathnet  mathscinet  zmath
[12]Borodin O. V., “Triangulated 3-polytopes with restricted minimal weight of faces”, Discrete Math, 186. (1998), 281–285  crossref  mathscinet  zmath
[13]Horňá M., Jendrol' S., “Unavoidable sets of face types for planar maps”, Discuss. Math. Graph Theory, 16:2 (1996), 123–142  crossref  mathscinet
[14]Borodin O. V. and Woodall D. R., “The weight of faces in plane maps”, Mat. Zametki, 6:5 (1998), 648–657  mathnet  crossref
[15]Avgustinovich S. V. and Borodin O. V., “Neighborhoods of edges in normal maps”, Diskretn. Anal. Issled. Oper., 2:3 (1995), 3–9  mathnet  mathscinet
[16]Jendrol' S., Voss H.-J., “Light subgraphs of graphs embedded in the plane - a survey”, Discrete Math, 313:4 (2013), 406–421  crossref  mathscinet  zmath  scopus
[17]Borodin O. V., “Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps”, Diskret. Mat., 3:4 (1991), 24–27  mathnet  mathscinet  zmath
[18]Borodin O. V. and Loparev D. V., “The height of small faces in planar normal maps”, Diskretn. Anal. Issled. Oper. Ser., 5:4 (1998), 6–17  mathnet  mathscinet  zmath
[19]Ferencová B., Madaras T., “On the structure of polyhedral graphs with prescribed edge and dual edge weight”, Acta Univ. M. Belii Math, 12 (2005), 13–18  mathscinet  zmath
[20]Ferencová B., Madaras T., “Light graph in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight”, Discrete Math, 310 (2010), 1661–1675  crossref  mathscinet  zmath  scopus
[21]Jendrol' S., “Triangles with restricted degrees of their boundary vertices in plane triangulations”, Discrete Math, 196. (1999), 177–196  crossref  mathscinet  zmath
[22]Madaras T., Soták R., “The 10-cycle C10 is light in the family of all plane triangulations with minimum degree five”, Tatra Mt. Math. Publ, 18 (1999), 35–56  mathscinet  zmath
[23]Madaras T., Skrekovski R., Voss H.-J., “The 7-cycle C7 is light in the family of planar graphs with minimum degree 5”, Discrete Math, 307 (2007), 1430–1435  crossref  mathscinet  zmath  scopus
[24]Mohar B., Skrekovski R., Voss H.-J., “Light subraphs in planar graphs of minimum degree 4 and edge-degree 9”, J. Graph Theory, 44 (2003), 261–295  crossref  mathscinet  zmath  scopus
[25]Madaras T., Skrekovski R., “Heavy paths, light stars, and big melons”, Discrete Math, 286 (2004), 115–131  crossref  mathscinet  zmath  scopus
[26]Borodin O. V., “An improvement of Lebesgue’s theorem on the structure of minor faces of 3-polytopes”, Diskretn. Anal. Issled. Oper., 9:3 (2002), 29–39  mathnet  zmath
[27]Borodin O. V., Ivanova A. O., “Describing 3-faces in normal plane maps with minimum degree 4”, Discrete Math, 313:23 (2013), 2841–2847  crossref  mathscinet  zmath  scopus
[28]Borodin O. V., Woodall D. R., “Cyclic degrees of 3-polytopes”, Graphs Comb., 15 (1999), 267–277  crossref  mathscinet  zmath
[29]Kotzig A., “Contribution to the theory of Eulerian polyhedra”, Mat.-Fyz. Cas., 5 (1955), 101–113  mathscinet
[30]Wernicke P., “Uber den kartographischen Vierfarbensatz”, Math. Ann, 58 (1904), 413–426  crossref  mathscinet  zmath  scopus
How to Cite
Ivanova, A. (2016) “Description of faces in 3-polytopes without vertices of degree from 4 to 9”, Mathematical notes of NEFU, 23(3), pp. 46-54. Available at: http://mzsvfu.ru/index.php/mz/article/view/description-of-faces-in-3-polytopes-without-vertices-of-degree-from-4-to-9 (Accessed: 22September2020).
Section
Mathematics