Light edges in degree-constrained graphs

Prosenjit Bose, Michiel Smid, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)


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 languageEnglish
Pages (from-to)35-41
Number of pages7
JournalDiscrete Mathematics
Issue number1-3
Publication statusPublished - 2004
Externally publishedYes

Cite this