# Light edges in 1-planar graphs with prescribed minimum degree

Discussiones Mathematicae Graph Theory (2012)

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

## Access Full Article

top## Abstract

top## How to cite

topDá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] 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] R. Diestel, Graph Theory, Springer, Graduate Texts in Mathematics 173 (2nd ed., Springer-Verlag, New York, 2000).
- [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] 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] 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] 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] 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] 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] S. Jendrol' and M. Tuhársky, A Kotzig type theorem for non-orientable surfaces, Math. Slovaca 56 (2006) 245-253. Zbl1141.05028
- [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] 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] S. Jendrol' and H.-J. Voss, Light subgraph.
- [13] E. Jucovič, Convex polytopes, Veda Bratislava, 1981 (in Slovak).
- [14] A. Kotzig, Contribution to the theory of Eulerian polyhedra, Math. Slovaca 5 (1955) 111-113.
- [15] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Sem. Univ. Hamburg 29 (1965) 107-117, doi: 10.1007/BF02996313. Zbl0132.20701
- [16] D.P. Sanders, On light edges and triangles in projective planar graphs, J. Graph Theory 21 (1996) 335-342. Zbl0854.05037

## NotesEmbed ?

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