Light edges in 1-planar graphs with prescribed minimum degree

Dávid Hudák; Peter Šugerek

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 3, page 545-556
  • ISSN: 2083-5892

Abstract

top
A graph is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree δ ≥ 4 contains an edge with degrees of its endvertices of type (4, ≤ 13) or (5, ≤ 9) or (6, ≤ 8) or (7,7). We also show that for δ ≥ 5 these bounds are best possible and that the list of edges is minimal (in the sense that, for each of the considered edge types there are 1-planar graphs whose set of types of edges contains just the selected edge type).

How to cite

top

Dávid Hudák, and Peter Šugerek. "Light edges in 1-planar graphs with prescribed minimum degree." Discussiones Mathematicae Graph Theory 32.3 (2012): 545-556. <http://eudml.org/doc/270992>.

@article{DávidHudák2012,
abstract = {A graph is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree δ ≥ 4 contains an edge with degrees of its endvertices of type (4, ≤ 13) or (5, ≤ 9) or (6, ≤ 8) or (7,7). We also show that for δ ≥ 5 these bounds are best possible and that the list of edges is minimal (in the sense that, for each of the considered edge types there are 1-planar graphs whose set of types of edges contains just the selected edge type).},
author = {Dávid Hudák, Peter Šugerek},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {light edge; 1-planar graph; crossing; discharging},
language = {eng},
number = {3},
pages = {545-556},
title = {Light edges in 1-planar graphs with prescribed minimum degree},
url = {http://eudml.org/doc/270992},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Dávid Hudák
AU - Peter Šugerek
TI - Light edges in 1-planar graphs with prescribed minimum degree
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 3
SP - 545
EP - 556
AB - A graph is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. We prove that each 1-planar graph of minimum degree δ ≥ 4 contains an edge with degrees of its endvertices of type (4, ≤ 13) or (5, ≤ 9) or (6, ≤ 8) or (7,7). We also show that for δ ≥ 5 these bounds are best possible and that the list of edges is minimal (in the sense that, for each of the considered edge types there are 1-planar graphs whose set of types of edges contains just the selected edge type).
LA - eng
KW - light edge; 1-planar graph; crossing; discharging
UR - http://eudml.org/doc/270992
ER -

References

top
  1. [1] 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
  2. [2] R. Diestel, Graph Theory, Springer, Graduate Texts in Mathematics 173 (2nd ed., Springer-Verlag, New York, 2000). 
  3. [3] I. Fabrici and S. Jendrol', An inequality concerning edges of minor weight in convex 3-polytopes, Discuss. Math. Graph Theory 16 (1996) 81-87, doi: 10.7151/dmgt.1024. Zbl0868.52004
  4. [4] I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math. 307 (2007) 854-865, doi: 10.1016/j.disc.2005.11.056. Zbl1111.05026
  5. [5] D. Hudák and T. Madaras, On local properties of 1-planar graphs with high minimum degree, Ars Math. Contemp. 4 (2011) 245-254. Zbl1237.05053
  6. [6] D. Hudák and T. Madaras, On local structure of 1-planar graphs of minimum degree 5 and girth 4, Discuss. Math. Graph Theory 29 (2009) 385-400, doi: 10.7151/dmgt.1454. Zbl1194.05025
  7. [7] 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
  8. [8] S. Jendrol' and I. Schiermeyer, On max-min problem concerning weights of edges, Combinatorica 21 (2001) 351-359, doi: 10.1007/s004930100001. Zbl1012.05091
  9. [9] S. Jendrol' and M. Tuhársky, A Kotzig type theorem for non-orientable surfaces, Math. Slovaca 56 (2006) 245-253. Zbl1141.05028
  10. [10] S. Jendrol', M. Tuhársky and H.-J. Voss, A Kotzig type theorem for large maps on surfaces, Tatra Mt. Math. Publ. 27 (2003) 153-162. Zbl1062.05044
  11. [11] S. Jendrol' and H.-J. Voss, Light subgraphs of graphs embedded in plane and projective plane - a survey, Preprint Inst. of Algebra MATH-AL-02-2001, TU Dresden. 
  12. [12] S. Jendrol' and H.-J. Voss, Light subgraph. 
  13. [13] E. Jucovič, Convex polytopes, Veda Bratislava, 1981 (in Slovak). 
  14. [14] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Math. Slovaca 5 (1955) 111-113. 
  15. [15] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Sem. Univ. Hamburg 29 (1965) 107-117, doi: 10.1007/BF02996313. Zbl0132.20701
  16. [16] D.P. Sanders, On light edges and triangles in projective planar graphs, J. Graph Theory 21 (1996) 335-342. Zbl0854.05037

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.