Premium
On Light Edges and Triangles in Planar Graphs of Minimum Degree Five
Author(s) -
Borodin Oleg V.,
Sanders Daniel P.
Publication year - 1994
Publication title -
mathematische nachrichten
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.913
H-Index - 50
eISSN - 1522-2616
pISSN - 0025-584X
DOI - 10.1002/mana.19941700103
Subject(s) - mathematics , planar graph , combinatorics , outerplanar graph , planar , graph , 1 planar graph , degree (music) , polyhedral graph , discrete mathematics , pathwidth , line graph , computer science , physics , computer graphics (images) , acoustics
This paper presents two tight inequalities for planar graphs of minimum degree five. An edge or face of a plane graph is light if the sum of the degrees of the vertices incident with it is small. A light edge inequality is presented which shows that planar graphs of minimum degree five have a large number of light edges; a graph is presented which shows that this inequality cannot be improved. This completes work contributed to by Wernicke , Grünbaum , Fisk , and Borodin . A graph is presented which shows that a similar light triangle inequality of Borodin is best possible; no such graph had been previously found.