Counting 1-factors in regular bipartite graphs
type: Item
instance of: scholarly article
title: Counting 1-factors in regular bipartite graphs
zbMATH Open document ID: 0905.05060
published in: Journal of Combinatorial Theory. Series B
publication date: 1998-12-20T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/2154
review text: 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}}}\).
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1154563
reviewed by: Brian Alspach
MaRDI profile type: Publication
OpenAlex ID: W1999344551
cites work: Q3936847
cites work: Q5562013
cites work: Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
cites work: A lower bound for the permanent of a doubly stochastic matrix
cites work: Matching theory
cites work: Q4184984
cites work: Q4039989
cites work: On the number of edge-colourings of regular bipartite graphs
cites work: Q3897156
cites work: Q4184837
DOI: 10.1006/JCTB.1997.1798
author: Alexander Schrijver
description: scientific article; zbMATH DE number 1154563