Discussiones Mathematicae Graph Theory 16(1) (1996) 81-87
DOI: https://doi.org/10.7151/dmgt.1024
AN INEQUALITY CONCERNING EDGES OF MINOR WEIGHT IN CONVEX 3-POLYTOPES
Igor Fabrici Institute of Mathematics, Technical University
Ilmenau |
Stanislav Jendrol' Department of Geometry and Algebra, P.J. afárik
University |
Dedicated to Professor E. Jucovic on the occasion of his 70th birthday.
Abstract
Let eij 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 20e3,3+25e3,4+16e3,5+10e3,6+6[2/3] e3,7+5e3,8+2[1/2] e3,9+2e3,10+16[2/3] e4,4+11e4,5+5e4,6+1[2/3]e4,7+5[1/3] e5,5+2e5,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.
Keywords: planar graph, convex 3-polytope, normal map.
1991 Mathematics Subject Classification: 52B10, 52B05, 05C10.
References
[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. |
Close