Timeline for A weaker version of Dirac's theorem
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 7, 2018 at 12:42 | vote | accept | Dominic van der Zypen | ||
| Aug 7, 2018 at 9:33 | comment | added | Peter Heinig | (And that bound is best possible in general, as evidenced by a triangle.) | |
| Aug 7, 2018 at 9:31 | comment | added | Peter Heinig | @the OP: it's worth pointing out that the size of the smallest maximal matching has been studied in the literature, rather rarely. E.g. Vesna Andova, František Kardoš, Riste Škrekovski: Sandwiching Saturation Number of Fullerene Graphs. MATCH Commun. Math. Comput. Chem. 73 (2015) . (arxiv.org/abs/1405.2197) have some results for fullerene-graphs (they mention the general fact that any graph $G$ has a maximal matching of size $\frac{n-\alpha(G)}{2}$). Since $\alpha\leq n-\delta$ in general, it follows that any graph has a maximal matching of size $\geq\frac12\delta(G)$. | |
| Aug 7, 2018 at 8:59 | comment | added | Philipp Lampe | @PeterHeinig: I see. Thanks for your explanations. | |
| Aug 7, 2018 at 8:58 | answer | added | Philipp Lampe | timeline score: 4 | |
| Aug 7, 2018 at 8:46 | comment | added | Peter Heinig | @PhilippLampe: $\bigcup M$ obviously means the union of a set as it 'Axiom of Union' in the ZF-axioms (en.wikipedia.org/wiki/Axiom_of_union). The OP's notation is correct. Re "equal to $M$ itself": no, that would be the equation $\bigcup\{M\} = M$. Regarding the substance of the question: I think your comment answers the question in the negative. Technically, this would merit making it an answer, though of course this depends on your taste regarding answering easy question. | |
| Aug 7, 2018 at 8:27 | comment | added | Philipp Lampe | I have a question concerning your notation $\bigcup M$. Isn't the union of a single set $M$ equal to $M$ itself (which is not a subset of $V$)? Or is this supposed to mean $\bigcup_{m\in M}m$? In this case, the left hand side is equal to the number of vertices that are not covered by $M$. However, the complete bipartite graph $G=K_{n+c+1,n}$ has $\delta(G)=n$ but every matching leaves at least $c+1$ vertices in the large independent set uncovered. | |
| Aug 7, 2018 at 6:12 | history | edited | Dominic van der Zypen |
edited tags
|
|
| Aug 7, 2018 at 5:44 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |