4
votes
2answers
184 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$ ...
0
votes
1answer
100 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 ...
0
votes
1answer
181 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 & ...
1
vote
1answer
86 views

Would a graph with such maximum weighted matchings exist?

Edit Tony's answer is quite nice, but I meant something else. Sorry for editing again, I meant edges. I am looking for a graph with 3 distinguished edges $xx'$,$yy'$,$zz'$ where ...
6
votes
1answer
377 views

How does this algorithmic proof of Edmonds-Gallai work?

Sorry, this is going to be technical and dirty. I am not looking for a proof of the Edmonds-Gallai structure theorem (I understand two of them, even if they are rather similar); I am trying to ...
3
votes
1answer
231 views

Degree conditions for k-factor

I am looking for a simple degree conditon that ensures the existence of a k-factor in a graph. The k is supposed to be relatively high and I don't mind the condition being a bit strict. Ideally, ...
2
votes
0answers
72 views

A non-distinct system of representative edges.

I have the following problem: Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_{i} E(G_{i}) ...
4
votes
0answers
145 views

Bounds on numbers of matchings of given sizes in bipartite graphs

I am interested in the following question: For which sets ${m_1,\ldots m_k}$ of positive integers do there exist bipartite graphs having exactly $m_i$ matchings of size $i$ for each $1\leq i \leq k$, ...
9
votes
2answers
468 views

Gale-Ryser stable marriage theorem: can we entrust matchmaking to monkeys?

Disclaimer: This is a question I have not done any real research about. I asked it myself some 5 years ago, and back then I had no idea where to start. Now I have some texts on stable matchings lying ...
6
votes
2answers
626 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 ...