On the effect of major vertices on the number of light edges

✍ Scribed by Sanders, Daniel P.

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 423 KB
• Volume: 21
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199603)21:3<317::aid-jgt6>3.0.co;2-t

✦ Synopsis

This paper presents an inequality satisfied by planar graphs of minimum degree five.

For the purposes of this paper, an edge of a graph is light if the weight of the edge, or the sum of the degrees of the vertices incident with it, is at most eleven. The inequality presented shows that planar graphs of minimum degree five have a large number of light edges. This inequality improves upon a recent inequality of Borodin and Sanders, which showed that 7/15 times the number of edges of weight 10 plus 1/5 times the number of edges of weight 11 is at least 12. These constants 7/15 and 1/5 were shown to be best possible. The inequality in this paper shows that, for this type of graph, the presence of vertices of degree at least eight increases the number of light edges. A graph is presented which shows that the coefficient obtained for the number of degree eight vertices is best possible.