Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-25T01:59:10.146Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximal matchings in graphs with given minimal and maximal degrees

Published online by Cambridge University Press:  24 October 2008

B. Bollobás  and
S. E. Eldridge
B. Bollobás
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Cambridge
S. E. Eldridge
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Cambridge
Get access Rights & Permissions [Opens in a new window]

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Berge, C.Sur le couplage maximum d'un graphe. C.R. Acad. Sci. 247 (1958), 258–259.Google Scholar
(2)Bollobás, B., Daykin, D. E. and ErdöS, P. Sets of independent edges in a hypergraph. Quart. J. Math. (Oxford). To appear.Google Scholar
(3)Erdös, P. and Pósa, L.On the maximal number of disjoint circuits in a graph. Publ. Math. Debrecen 9 (1962), 3–12.CrossRefGoogle Scholar
(4)Harary, F.Graph Theory (Addison-Wesley; Reading, Mass. 1969).CrossRefGoogle Scholar
(5)Petersen, J.Die theorie der regulären Graphen. Acta Math. 15 (1891), 193–220.Google Scholar
(6)Tutte, W. T.The factorisation of linear graphs. J. London Math. Soc. 22 (1947), 107–111.Google Scholar
(7)Weinstern, J. H.On the number of disjoint edges in a graph. Canad. J. Math. 15 (1963), 106–111.CrossRefGoogle Scholar