1. ON THE NUMBER OF PERFECT MATCHINGS IN A BIPARTITE GRAPH.
- Author
-
DE CARVALHO, MARCELO H., LUCCHESI, CLÄUDIO L., and MURTY, U. S. R.
- Subjects
- *
BIPARTITE graphs , *MATHEMATICAL bounds , *GRAPH theory , *INTEGERS , *MATHEMATICS - 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]
- Published
- 2013
- Full Text
- View/download PDF