An inequality concerning edges of minor weight in convex 3-polytopes

• Autorzy: Igor Fabrici , Stanislav Jendrol'
• Języki publikacji: EN

Abstrakty

EN

Let $e_{ij}$ be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is $20e_{3,3} + 25e_{3,4} + 16e_{3,5} + 10e_{3,6} + 6[2/3]e_{3,7} + 5e_{3,8} + 2[1/2]e_{3,9} + 2e_{3,10} + 16[2/3]e_{4,4} + 11e_{4,5} + 5e_{4,6} + 1[2/3]e_{4,7} + 5[1/3]e_{5,5} + 2e_{5,6} ≥ 120$; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.

Słowa kluczowe

EN

planar graph; convex 3-polytope; normal map

Kategorie tematyczne

• 05C10: Planar graphs; geometric and topological aspects of graph theory
• 52B05: Combinatorial properties (number of faces, shortest paths, etc.)
• 52B10: Three-dimensional polytopes

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1996
• Tom: 16
• Numer: 1
• Strony: 81-87

Daty

wydano

1996

otrzymano

1996-01-24

poprawiono

1996-04-15

Twórcy

autor

Igor Fabrici

• Institute of Mathematics, Technical University Ilmenau, PF 327, D-98684 Ilmenau, Germany

autor

Stanislav Jendrol'

• Department of Geometry and Algebra, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic

Bibliografia

• [1] O. V. Borodin, Computing light edges in planar graphs, in: R. Bodendiek, R. Henn, eds., Topics in Combinatorics and Graph Theory (Physica-Verlag, Heidelberg, 1990) 137-144.
• [2] O. V. Borodin, Structural properties and colorings of plane graphs, Ann. Discrete Math. 51 (1992) 31-37, doi: 10.1016/S0167-5060(08)70602-2.
• [3] O. V. Borodin, Precise lower bound for the number of edges of minor weight in planar maps, Math. Slovaca 42 (1992) 129-142.
• [4] O. V. Borodin, Structural properties of planar maps with the minimal degree 5, Math. Nachr. 158 (1992) 109-117, doi: 10.1002/mana.19921580108.
• [5] O. V. Borodin and D. P. Sanders, On light edges and triangles in planar graph of minimum degree five, Math. Nachr. 170 (1994) 19-24, doi: 10.1002/mana.19941700103.
• [6] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390-408, doi: 10.1007/BF02764716.
• [7] B. Grünbaum, Polytopal graphs, in: D. R. Fulkerson, ed., Studies in Graph Theory, MAA Studies in Mathematics 12 (1975) 201-224.
• [8] B. Grünbaum, New views on some old questions of combinatorial geometry, Int. Teorie Combinatorie, Rome, 1973, 1 (1976) 451-468.
• [9] B. Grünbaum and G. C. Shephard, Analogues for tiling of Kotzig's theorem on minimal weights of edges, Ann. Discrete Math. 12 (1982) 129-140.
• [10] J. Ivančo, The weight of a graph, Ann. Discrete Math. 51 (1992) 113-116, doi: 10.1016/S0167-5060(08)70614-9.
• [11] J. Ivančo and S. Jendrol', On extremal problems concerning weights of edges of graphs, in: Coll. Math. Soc. J. Bolyai, 60. Sets, Graphs and Numbers, Budapest (Hungary) 1991 (North Holland, 1993) 399-410.
• [12] E. Jucovič, Strengthening of a theorem about 3-polytopes, Geom. Dedicata 3 (1974) 233-237, doi: 10.1007/BF00183214.
• [13] E. Jucovič, Convex 3-polytopes (Veda, Bratislava, 1981, Slovak).
• [14] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. as. SAV (Math. Slovaca) 5 (1955) 101-103 (Slovak; Russian summary).
• [15] A. Kotzig, From the theory of Euler's polyhedra, Mat. as. (Math. Slovaca) 13 (1963) 20-34 (Russian).
• [16] O. Ore, The four-color problem (Academic Press, New York, 1967).
• [17] J. Zaks, Extending Kotzig's theorem, Israel J. Math. 45 (1983) 281-296, doi: 10.1007/BF02804013.

Identyfikatory

DOI

10.7151/dmgt.1024