Counting 1-factors in regular bipartite graphs (Q1386423): Difference between revisions

The author proves that any \(k\)-regular bipartite graph with \(2n\) vertices has at least \(({(k-1)^{k-1}\over{k^ {k-2}}})^n\) 1-factors. This generalizes an earlier result of \textit{M. Voorhoeve} [A lower bound for the permanents of certain \((0,1)\)-matrices, Indag. Math. 41, 83-86 (1979; Zbl 0401.05005)], in which it was shown a cubic bipartite graph has at least \(({4\over 3})^n\) 1-factors. This also establishes that \( {(k-1)^{k-1}}\over{k^{k-2}}\) is the best base possible. That is, if \(\alpha_k\) is the largest real number such that any \(k\)-regular bipartite graph with \(2n\) vertices has at least \(\alpha_k^n\) 1-factors, then \(\alpha_k = {{(k-1)^{k-1}}\over{k^{k-2}}}\).