✦ LIBER ✦

On Light Edges and Triangles in Planar Graphs of Minimum Degree Five

✍ Scribed by Oleg V. Borodin; Daniel P. Sanders

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 342 KB
Volume: 170
Category: Article
ISSN: 0025-584X
DOI: 10.1002/mana.19941700103

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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.

📜 SIMILAR VOLUMES

On light edges and triangles in projecti

On light edges and triangles in projective planar graphs

✍ Sanders, Daniel P. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 376 KB 👁 2 views

An edge or face of an embedded graph is light if the sum of the degrees of the vertices incident with it is small. This paper parallelizes four inequalities on the number of light edges and light triangles from the plane to the projective plane. Each of the four inequalities is shown to be the best

Light subgraphs in planar graphs of mini

Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9

✍ B. Mohar; R. Škrekovski; H.-J. Voss 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

## Abstract A graph __H__ is light in a given class of graphs if there is a constant __w__ such that every graph of the class which has a subgraph isomorphic to __H__ also has a subgraph isomorphic to __H__ whose sum of degrees in __G__ is ≤ __w__. Let $\cal G$ be the class of simple planar graphs