All Questions
Tagged with perfect-matchings matching-theory
56 questions
5
votes
0
answers
249
views
Counting perfect matchings with integrals
Has anyone used the Joni-Rota-Godsil integral formula (see details below) to count perfect matchings of square-grid graphs, Aztec diamond graphs, hexagon-honeycomb graphs, etc.? (Or even just to ...
- 19.7k
1
vote
1
answer
190
views
Converse of Petersen's 2-Factorization Theorem
Definition: A $k$-factor of a graph is a spanning $k$-regular
subgraph.
Definition: A $k$-factorization of a graph is a partition of the edge
set into $k$-factors.
Petersen's celebrated ...
- 6,962
0
votes
1
answer
773
views
Counting matchings in a bipartite matching-covered graph
A graph is called matching-covered if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by Lovasz & Plummer)....
- 6,962
3
votes
1
answer
131
views
A graph $G$ with two $K_6$ subgraphs, in which any one-factor of $G$ induces a one-factor in exactly one of the $K_6$ subgraphs?
I'm seeking a simple graph $G$ of the following type:
It contains two disjoint copies of $K_6$ (the complete graph on 6 nodes), $H$ and $H'$ say.
Any one-factor of $G$ must contain either (a) a one ...
- 4,229
6
votes
1
answer
230
views
A non-distinct system of representative edges
I have the following problem:
Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs on the same vertex set. I would like to find a "system of representative edges" $ f : \mathcal{G} \...
- 161
8
votes
1
answer
2k
views
Condition on a bipartite graph to have an $m$-factor
This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago.
Let $G$ be a bipartite graph, i. e., a graph ...
- 33.8k