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

Igor Fabrici; Stanislav Jendrol'

Discussiones Mathematicae Graph Theory (1996)

  • Volume: 16, Issue: 1, page 81-87
  • ISSN: 2083-5892

Abstract

top
Let e i j 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 20 e 3 , 3 + 25 e 3 , 4 + 16 e 3 , 5 + 10 e 3 , 6 + 6 [ 2 / 3 ] e 3 , 7 + 5 e 3 , 8 + 2 [ 1 / 2 ] e 3 , 9 + 2 e 3 , 10 + 16 [ 2 / 3 ] e 4 , 4 + 11 e 4 , 5 + 5 e 4 , 6 + 1 [ 2 / 3 ] e 4 , 7 + 5 [ 1 / 3 ] e 5 , 5 + 2 e 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.

How to cite

top

Igor Fabrici, and Stanislav Jendrol'. "An inequality concerning edges of minor weight in convex 3-polytopes." Discussiones Mathematicae Graph Theory 16.1 (1996): 81-87. <http://eudml.org/doc/270533>.

@article{IgorFabrici1996,
abstract = {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.},
author = {Igor Fabrici, Stanislav Jendrol'},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; convex 3-polytope; normal map; edge weights; planar maps; normal planar map; 3-connected planar map; Kotzig's theorem; Steinitz's theorem},
language = {eng},
number = {1},
pages = {81-87},
title = {An inequality concerning edges of minor weight in convex 3-polytopes},
url = {http://eudml.org/doc/270533},
volume = {16},
year = {1996},
}

TY - JOUR
AU - Igor Fabrici
AU - Stanislav Jendrol'
TI - An inequality concerning edges of minor weight in convex 3-polytopes
JO - Discussiones Mathematicae Graph Theory
PY - 1996
VL - 16
IS - 1
SP - 81
EP - 87
AB - 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.
LA - eng
KW - planar graph; convex 3-polytope; normal map; edge weights; planar maps; normal planar map; 3-connected planar map; Kotzig's theorem; Steinitz's theorem
UR - http://eudml.org/doc/270533
ER -

References

top
  1. [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. Zbl0705.05023
  2. [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. Zbl0765.05043
  3. [3] O. V. Borodin, Precise lower bound for the number of edges of minor weight in planar maps, Math. Slovaca 42 (1992) 129-142. Zbl0767.05039
  4. [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. Zbl0776.05035
  5. [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. Zbl0813.05020
  6. [6] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390-408, doi: 10.1007/BF02764716. Zbl0265.05103
  7. [7] B. Grünbaum, Polytopal graphs, in: D. R. Fulkerson, ed., Studies in Graph Theory, MAA Studies in Mathematics 12 (1975) 201-224. Zbl0323.05104
  8. [8] B. Grünbaum, New views on some old questions of combinatorial geometry, Int. Teorie Combinatorie, Rome, 1973, 1 (1976) 451-468. 
  9. [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. Zbl0504.05026
  10. [10] J. Ivančo, The weight of a graph, Ann. Discrete Math. 51 (1992) 113-116, doi: 10.1016/S0167-5060(08)70614-9. Zbl0773.05066
  11. [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. [12] E. Jucovič, Strengthening of a theorem about 3-polytopes, Geom. Dedicata 3 (1974) 233-237, doi: 10.1007/BF00183214. Zbl0297.52006
  13. [13] E. Jucovič, Convex 3-polytopes (Veda, Bratislava, 1981, Slovak). 
  14. [14] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Mat.-Fyz. as. SAV (Math. Slovaca) 5 (1955) 101-103 (Slovak; Russian summary). 
  15. [15] A. Kotzig, From the theory of Euler's polyhedra, Mat. as. (Math. Slovaca) 13 (1963) 20-34 (Russian). Zbl0134.19601
  16. [16] O. Ore, The four-color problem (Academic Press, New York, 1967). Zbl0149.21101
  17. [17] J. Zaks, Extending Kotzig's theorem, Israel J. Math. 45 (1983) 281-296, doi: 10.1007/BF02804013. Zbl0524.05031

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.