Article contents
Maximal matchings in graphs with given minimal and maximal degrees
Published online by Cambridge University Press: 24 October 2008
Abstract
In this note we determine the greatest lower bound of the number of independent edges in a graph in terms of the number of vertices, the minimal degree and the maximal degree. More generally we examine the greatest lower bound of the number of independent edges in a K-connected (or λ-edge-connected) graph with given number of vertices and given minimal and maximal degrees. These results extend those of Erdös and Pósa (3) and Weinstein (7). Our proof makes heavy use of Berge's slight extension of Tutte's characterization of graphs with 1-factors.
- Type
- Research Article
- Information
- Mathematical Proceedings of the Cambridge Philosophical Society , Volume 79 , Issue 2 , March 1976 , pp. 221 - 234
- Copyright
- Copyright © Cambridge Philosophical Society 1976
References
REFERENCES
- 13
- Cited by