Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-26T13:40:18.153Z Has data issue: false hasContentIssue false
  • English
  • Français

Large Matchings in Graphs

Published online by Cambridge University Press:  20 November 2018

J. Weinstein
J. Weinstein*
Affiliation:
St. Mary's College of Maryland, St. Mary's City, Maryland
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

How large a matching must a graph have?

We consider graphs G (finite, undirected, with no loops or multiple edges), with order nG (always ≧ 1) and mG the maximum number of edges in a matching of G. The matchability μG of G is the fraction (2m/n) of nodes covered by a maximum matching.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 26 , Issue 6 , December 1974 , pp. 1498 - 1508
Copyright
Copyright © Canadian Mathematical Society 1974

References

1. Berge, C., The theory of graphs and its applications (Methuen, London, 1962; reprinted 1966).Google Scholar
2. Moon, J., On independent complete subgraphs in a graph, Can. J. Math. 20 (1968), 95–102.Google Scholar
3. Ore, O., The four-color problem (Academic Press, New York-London, 1967).Google Scholar
4. Weinstein, J., On the number of disjoint edges in a graph, Can. J. Math. 15 (1963), 106–111.Google Scholar