×

zbMATH — the first resource for mathematics

The vertex-face weight of edges in 3-polytopes. (English. Russian original) Zbl 1331.52018
Sib. Math. J. 56, No. 2, 275-284 (2015); translation from Sib. Mat. Zh. 56, No. 2, 338-350 (2015).
Summary: The weight \(w(e)\) of an edge \(e\) in a 3-polytope is the maximum degree-sum of the two vertices and two faces incident with \(e\). In 1940, Lebesgue proved that each 3-polytope without the so-called pyramidal edges has an edge \(e\) with \(w(e) \leq 21\). In 1995, this upper bound was improved to 20 by Avgustinovich and Borodin. Note that each edge of the \(n\)-pyramid is pyramidal and has weight \(n + 9\). Recently, we constructed a 3-polytope without pyramidal edges satisfying \(w(e) \geq 18\) for each \(e\). The purpose of this paper is to prove that each 3-polytope without pyramidal edges has an edge \(e\) with \(w(e) \leq 18\). In other terms, this means that each plane quadrangulation without a face incident with three vertices of degree 3 has a face with the vertex degree-sum at most 18, which is tight.

MSC:
52B10 Three-dimensional polytopes
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Steinitz, E., Polyheder und raumeinteilungen, Enzykl. Math. Wiss. (Geometrie), 3, 1-139, (1922)
[2] Lebesgue, H., Quelques conséquences simples de la formule d’euler, J. Math. Pures Appl., 19, 27-43, (1940) · Zbl 0024.28701
[3] Avgustinovich, S. V.; Borodin, O. V., Neighborhoods of edges in normal maps, Diskret. Anal. Issled. Oper., 2, 3-9, (1995) · Zbl 0856.05031
[4] Borodin, O. V.; Ivanova, A. O., The height of edge in 3-polytope, Siberian Elektron. Mat. Izv., 11, 457-463, (2014) · Zbl 1326.05060
[5] Borodin, O. V., Colorings of plane graphs: a survey, Discrete Math., 313, 517-539, (2013) · Zbl 1259.05042
[6] Ore, O.; Plummer, M. D.; Tutte, W. T. (ed.), Cyclic coloration of plane graphs, 287-293, (1969), New York
[7] Plummer, M. D.; Toft, B., Cyclic coloration of 3-polytopes, J. Graph Theory, 11, 507-515, (1987) · Zbl 0655.05030
[8] Kotzig, A., From the theory of Eulerian polyhedra, Mat. Čas., 13, 20-34, (1963) · Zbl 0134.19601
[9] Borodin, O. V., Solving the kotzig and grünbaum problems on the separability of a cycle in planar graphs, Mat. Zametki, 46, 9-12, (1989) · Zbl 0694.05027
[10] Grünbaum, B., Polytopal graphs, Studies in Graph Theory, 12, 201-224, (1975) · Zbl 0323.05104
[11] Plummer, M. D., On the cyclic connectivity of planar graphs, 235-242, (1972), Berlin · Zbl 0247.05113
[12] Kotzig, A., Extremal polyhedral graphs, Ann. New York Acad. Sci., 319, 569-570, (1979)
[13] Borodin, O. V., Minimal weight of a face in planar triangulations without 4-vertices, Mat. Zametki, 51, 11-13, (1992) · Zbl 0755.05091
[14] Borodin, O. V., Triangulated 3-polytopes with restricted minimal weight of faces, Discrete Math., 186, 281-285, (1998) · Zbl 0956.52010
[15] Horňák, M.; Jendrol’, S., Unavoidable sets of face types for planar maps, Discus. Math. Graph Theory, 16, 123-142, (1996) · Zbl 0877.05048
[16] Borodin, O. V.; Woodall, D. R., The weight of faces in plane maps, Mat. Zametki, 64, 648-657, (1998) · Zbl 0958.52015
[17] Jendrol’, S.; Voss, H.-J., Light subgraphs of graphs embedded in the plane and in the projective plane: a survey, Discrete Math., 313, 406-421, (2013) · Zbl 1259.05045
[18] Borodin, O. V., Joint generalization of the theorems of Lebesgue and kotzig on the combinatorics of planar maps, Diskret. Mat., 3, 24-27, (1991) · Zbl 0742.05034
[19] Borodin, O. V.; Loparev, D. V., The height of small faces in planar normal maps, Diskretn. Anal. Issled. Oper., 5, 6-17, (1998) · Zbl 0913.05039
[20] Borodin, O. V.; Woodall, D. R., Cyclic degrees of 3-polytopes, Graphs Comb., 15, 267-277, (1999) · Zbl 0930.05055
[21] Ferencová, B.; Madaras, T., On the structure of polyhedral graphs with prescribed edge and dual edge weight, Acta Univ. M. Belii Math., 12, 13-18, (2005) · Zbl 1103.05026
[22] 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, 1661-1675, (2010) · Zbl 1222.05217
[23] Jendrol’, S., Triangles with restricted degrees of their boundary vertices in plane triangulations, Discrete Math., 196, 177-196, (1999) · Zbl 0934.05044
[24] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. Fyz. Casopis, 5, 101-113, (1955)
[25] Madaras, T.; Škrekovski, R., Heavy paths, light stars, and big melons, Discrete Math., 286, 115-131, (2004) · Zbl 1053.05035
[26] Madaras, T.; Soták, R., The 10-cycle is light in the family of all plane triangulations with minimum degree five, Tatra Mt. Math. Publ., 18, 35-56, (1999) · Zbl 0951.05031
[27] Madaras, T.; Škrekovski, R.; Voss, H.-J., The 7-cycle C7 is light in the family of planar graphs with minimum degree 5, Discrete Math., 307, 1430-1435, (2007) · Zbl 1115.05022
[28] Mohar, B.; Škrekovski, R.; Voss, H.-J., Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9, J. Graph Theory, 44, 261-295, (2003) · Zbl 1031.05075
[29] Wernicke, P., Über den kartographischen vierfarbensatz, Math. Ann., 58, 413-426, (1904) · JFM 35.0511.01
[30] Borodin, O. V., Strengthening lebesgue’s theorem on the structure of the minor faces in convex polyhedra, Diskretn. Anal. Issled. Oper. Ser. 1, 9, 29-39, (2002) · Zbl 1015.52008
[31] Borodin, O. V.; Ivanova, A. O., Describing 3-faces in normal plane maps with minimum degree 4, Discrete Math., 313, 2841-2847, (2013) · Zbl 1281.05054
[32] Borodin, O. V.; Ivanova, A. O.; Kostochka, A. V., Describing faces in plane triangulations, Discrete Math., 319, 47-61, (2014) · Zbl 1280.05027
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.