✦ LIBER ✦

Counting 1-Factors in Regular Bipartite Graphs

✍ Scribed by Alexander Schrijver

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 325 KB
Volume: 72
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1798

No coin nor oath required. For personal study only.

✦ Synopsis

We show that any k-regular bipartite graph with 2n vertices has at least \ (k&1) k&1 k k&2 + n perfect matchings (1-factors). Equivalently, this is a lower bound on the permanent of any nonnegative integer n_n matrix with each row and column sum equal to k. For any k, the base (k&1) k&1 Âk k&2 is largest possible.

1998 Academic Press

Here, the inequality was shown in [10], where moreover equality was conjectured for all k. That this conjecture is true is thus the result of the present paper. For completeness, we sketch the argument showing in (2) in Section 3 below.

📜 SIMILAR VOLUMES

Regular factors in K1,3-free graphs

✍ S. A. Choudum; M. S. Paulraj 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 1 views

## Abstract We show that every connected __K__~1,3~‐free graph with minimum degree at least __2k__ contains a __k__‐factor and construct connected __K__~1,3~‐free graphs with minimum degree __k__ + __0__(√__k__) that have no __k__‐factor.

Regular factors in K1,n free graphs

✍ Yoshimi Egawa; Katsuhiro Ota 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 280 KB

## Abstract A graph is said to be __K__~1,__n__~‐free, if it contains no __K__~1,__n__~ as an induced subgraph. We prove that for __n__ ⩾ 3 and __r__ ⩾ __n__ −1, if __G__ is a __K__~1,__n__~‐free graph with minimum degree at least (__n__^2^/4(__n__ −1))__r__ + (3__n__ −6)/2 + (__n__ −1)/4__r__, the

2-factors in random regular graphs

✍ Robalewska, Hanna D. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB 👁 3 views

In this paper the expectation and variance of the number of 2-factors in random r-regular graphs for any fixed r 2 3 is analyzed and the asymptotic distribution of this variable is determined.

1-Factorizations of random regular graph

1-Factorizations of random regular graphs

✍ M. S. O. Molloy; H. Robalewska; R. W. Robinson; N. C. Wormald 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 204 KB 👁 2 views

It is shown that for each r G 3, a random r-regular graph on 2 n vertices is equivalent in a certain sense to a set of r randomly chosen disjoint perfect matchings of the 2 n vertices, as n ª ϱ. This equivalence of two sequences of probabilistic spaces, called contiguity, occurs when all events almo

Generating and Counting Hamilton Cycles

Generating and Counting Hamilton Cycles in Random Regular Graphs

✍ Alan Frieze; Mark Jerrum; Michael Molloy; Robert Robinson; Nicholas Wormald 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 216 KB

Let G be chosen uniformly at random from the set G G r, n of r-regular graphs w x Ž . with vertex set n . We describe polynomial time algorithms that whp i find a Ž . Hamilton cycle in G, and ii approximately count the number of Hamilton cycles in G.

Restricted b-factors in bipartite graphs

Restricted b-factors in bipartite graphs and t-designs

✍ Ivette Arámbula; Illya V. Hicks 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 178 KB

## Abstract We present a new equivalence result between restricted __b__‐factors in bipartite graphs and combinatorial __t__‐designs. This result is useful in the construction of __t__‐designs by polyhedral methods. We propose a novel linear integer programming formulation, which we call GDP, for t