Abstract
Let α denote the average degree, and δ denote the minimum degree of a graph. An edge is light if both its endpoints have degree bounded by a constant depending only on α and δ. A graph is degree-constrained if α<2δ. The primary result of this paper is that every degree-constrained graph has a light edge. Most previous results in this direction have been for embedded graphs. This result is extended in a variety of ways. First it is proved that there exists a constant c(α,δ) such that for every 0≤<c(α,δ), every degree-constrained graph with n vertices has at least ε·n light edges. An analogous result is proved guaranteeing a matching of light edges. The method is refined in the case of planar graphs to obtain improved degree bounds.
Original language | English |
---|---|
Pages (from-to) | 35-41 |
Number of pages | 7 |
Journal | Discrete Mathematics |
Volume | 282 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 2004 |
Externally published | Yes |