PDF
Discussiones Mathematicae Graph Theory 32(3) (2012)
545-556
DOI: https://doi.org/10.7151/dmgt.1625
Light Edges in 1-planar Graphs with Prescribed Minimum Degree
Dávid Hudák and Peter Šugerek
Institute of Mathematics, Faculty of Science, |
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).
Keywords: light edge, 1-planar graph
2010 Mathematics Subject Classification: 05C10.
References
[1] | O.V. Borodin, Precise lower bound for the number of edges of minor weight in planar maps, Math. Slovaca 42 (1992) 129--142. |
[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. |
[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. |
[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. |
[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. |
[7] | J. Ivančo, The weight of a graph, Ann. Discrete Math. 51 (1992) 113--116, doi: 10.1016/S0167-5060(08)70614-9. |
[8] | S. Jendrol' and I. Schiermeyer, On max-min problem concerning weights of edges, Combinatorica 21 (2001) 351--359, doi: 10.1007/s004930100001. |
[9] | S. Jendrol' and M. Tuhársky, A Kotzig type theorem for non-orientable surfaces, Math. Slovaca 56 (2006) 245--253. |
[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. |
[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. |
[16] | D.P. Sanders, On light edges and triangles in projective planar graphs, J. Graph Theory 21 (1996) 335--342. |
Received 3 March 2011
Revised 29 September 2011
Accepted 29 September 2011
Close