| 1. |
- Aaghabali, M., et al.
(författare)
-
Upper bounds on the number of perfect matchings and directed 2-factors in graphs with given number of vertices and edges
- 2015
-
Ingår i: European journal of combinatorics (Print). - : Elsevier BV. - 0195-6698 .- 1095-9971. ; 45, s. 132-144
-
Tidskriftsartikel (refereegranskat)abstract
- We give an upper bound on the number of perfect matchings in simple graphs with a given number of vertices and edges. We apply this result to give an upper bound on the number of 2-factors in a directed complete bipartite balanced graph on 2n vertices. The upper bound is sharp for even n. For odd n we state a conjecture on a sharp upper bound.
|
|
| 2. |
- Friedland, S., et al.
(författare)
-
On the number of matching in regular graphs
- 2008
-
Ingår i: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 15:1
-
Tidskriftsartikel (refereegranskat)abstract
- For the set of graphs with a given degree sequence, consisting of any number of 2's and 1's, and its subset of bipartite graphs, we characterize the optimal graphs who maximize and minimize the number of m-matchings. We find the expected value of the number of m-matchings of r-regular bipartite graphs on 2n veritces with respect to the two standard measures. We state and discuss the conjectured upper and lower bounds for m-matchings in r-regular bipartite graphs on 2n vertices, and their asymptotic versions for infinite r-regular bipartite graphs. We prove these conjectures for 2-regular bipartite graphs and for m-matchings with m <= 4.
|
|
| 3. |
|
|
| 4. |
- Friedland, S., et al.
(författare)
-
On the Validations of the Asymptotic Matching Conjectures
- 2008
-
Ingår i: Journal of statistical physics. - : Springer. - 0022-4715 .- 1572-9613. ; 133:3, s. 513-533
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we review the asymptotic matching conjectures for r-regular bipartite graphs, and their connections in estimating the monomer-dimer entropies in d-dimensional integer lattice and Bethe lattices. We prove new rigorous upper and lower bounds for the monomer-dimer entropies, which support these conjectures. We describe a general construction of infinite families of r-regular tori graphs and give algorithms for computing the monomer-dimer entropy of density p, for any p is an element of[0,1], for these graphs. Finally we use tori graphs to test the asymptotic matching conjectures for certain infinite r-regular bipartite graphs.
|
|
