Back to Search
Start Over
ON THE NUMBER OF PERFECT MATCHINGS IN A BIPARTITE GRAPH.
- Source :
-
SIAM Journal on Discrete Mathematics . 2013, Vol. 27 Issue 2, p940-958. 19p. - Publication Year :
- 2013
-
Abstract
- In this paper we show that, with 11 exceptions, any matching covered bipartite graph on n vertices, with minimum degree greater than two, has at least 2n - 4 perfect matchings. Using this bound, which is the best possible, and McCuaig's theorem [W. McCuaig, J. Graph Theory, 38 (2001), pp. 124-169] on brace generation, we show that any brace on n vertices has at least (n-2)²/8 perfect matchings. A bi-wheel on n vertices has (n - 2)²/4 perfect matchings. We conjecture that there exists an integer such that every brace on n ≥ N vertices has at least (n-2)²/4 perfect matchings. [ABSTRACT FROM AUTHOR]
- Subjects :
- *BIPARTITE graphs
*MATHEMATICAL bounds
*GRAPH theory
*INTEGERS
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 27
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 89041351
- Full Text :
- https://doi.org/10.1137/120865938