On the Number of Matchings in Regular Graphs

No Thumbnail Available
Authors
Shmuel Friedland
Elliot Krop
Klas Markstrom
Issue Date
Type
Journal Article, Academic Journal
Language
Keywords
Research Projects
Organizational Units
Journal Issue
Alternative Title
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$ vertices 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\le 4$.
Description
Citation
Publisher
License
Journal
Volume
Issue
PubMed ID
DOI
ISSN
EISSN
Collections