All Questions
Tagged with matching-theory graph-theory
20 questions
21
votes
2
answers
4k
views
Graphs with only disjoint perfect matchings
Let $G(V,E)$ be a graph. I am searching for graphs with only disjoint perfect matchings (i.e. every edge only appears in at most one of the perfect matchings).
Examples:
Cyclic graph $C_n$ with even ...
- 155
2
votes
1
answer
401
views
Perfect matchings in infinite graphs
Let $G=(V,E)$ be an infinite graph such that $|V| = \kappa$ for some infinite cardinal $\kappa$, and every $v\in V$ has degree $\kappa$. Does $G$ have a perfect matching?
- 48.8k
7
votes
2
answers
480
views
Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?
Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be $\...
- 13.9k
3
votes
1
answer
3k
views
Number of perfect matchings in bipartite graph with given minimum degree
Let $G$ be a spanning subgraph of $K_{n,n}$ with minimum degree $\delta(G) \geq n/2$. It's easy to show using Hall's theorem that $G$ has a perfect matching, and the example of two disjoint copies of ...
- 4,589
2
votes
2
answers
353
views
Matching with probabilistic edges
Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...
- 239
-1
votes
2
answers
306
views
Cardinality of a set of mutually disjoint perfect matchings of $K_\omega$
If $G=(V,E)$ is a simple, undirected graph, we say that $M\subseteq E$ is a perfect matching if the members of $M$ are pairwise disjoint and $\bigcup M = V$. Let $K_\omega$ be the complete graph on $\...
- 48.8k
30
votes
2
answers
3k
views
An unfair marriage lemma
I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:
Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
- 32.4k
15
votes
3
answers
613
views
Maximum matching in a graph with no "shortcuts"
For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^...
- 34.3k
8
votes
2
answers
759
views
Maximum number of perfect matchings in a planar graph?
What is the maximum number of perfect matchings a planar $k$-partite $|V|$ number of vertices simple graph can have where $k=2,3,4$ ($k>4$ is impossible for a planar graph)?
Since number of ...
- 13.9k
7
votes
1
answer
969
views
Graph to Bipartite conversion preserving number of perfect matchings
Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that ...
- 13.9k
7
votes
1
answer
952
views
Roots of matching polynomial of graph
At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...
- 674
7
votes
3
answers
393
views
Perfect matchings of a regular, uniform, partite hypergraph
This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically ...
6
votes
2
answers
7k
views
How many perfect matchings in a regular bipartite graph?
We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$.
What is an upper bound on the number of perfect matchings of $G$?
- 61
6
votes
0
answers
296
views
Catalan numbers from matchings?
There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph.
My question is:
Is there a family of graphs $G_1,G_2,\dotsc$ with the number of ...
- 15.8k
3
votes
1
answer
778
views
Equitable edge coloring of graphs
Consider a simple regular graph $G$ with $n$ vertices and $E$ edges. Then, can we say that the edges can be colored equitably in $\Delta+1$ colors? By equitability is meant that a proper $\Delta+1$ ...
- 2,089
3
votes
1
answer
205
views
Does there exist an r-regular graph (r≥2) with a unique maximum matching?
Akbari, Ghodrati, Hosseinzadeh (2017), On the structure of graphs having a unique k-factor, Aust. J. Combin. (pdf) show:
... we prove that there is no r-regular graph (r≥2) with a unique perfect ...
- 1,327
3
votes
1
answer
99
views
Maximal matchings in connected graphs
Let $n\in\mathbb{N}$ be a positive integer. Is there a connected graph $G$ such that $G$ cannot be coloured with less than $n$ colours, and every two maximal matchings have non-empty intersection?
(I ...
- 48.8k
3
votes
1
answer
304
views
Perfect matchings in infinite regular bipartite graphs
This question was motivated by a discussion here and is related to a previous question here.
Let $\kappa$ and $\lambda$ be cardinals such that $0<\lambda\leq \kappa$. Let $G=(A\cup B, E)$ be a ...
- 1,701
2
votes
0
answers
186
views
Induced matchings in a bipartite graph with every matching having the same number of edges
Suppose $n,k$ are positive integers such that $k\mid n$.
Consider a bipartite graph $H=(A,B,E)$ such that $|A|=|B|=n$ and the edge set $E$ consists of the union of $m(H)$ induced matchings with every ...
- 1,997
-1
votes
1
answer
378
views
Marriages in infinite bipartite graphs with many neighbors
Let $A,B\neq \emptyset$ be disjoint and suppose $G = (A\cup B, E)$ is bipartite where for all $e\in E$ we have $e\cap A \neq \emptyset\neq e\cap B$. For $a\in A$ we set $N_G(a) = \{b\in B: (\exists e\...
- 48.8k