Timeline for Graphs with only disjoint perfect matchings
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 6, 2021 at 17:35 | comment | added | Peter Taylor | Ah! I failed to pick up on the subscripting of the $v$s implying that the graph has $2n$ vertices rather than the more conventional $n$. (My observation about the assumption of a simple graph was addressed at MarioKrenn rather than you, hence the at-name). | |
| Jul 6, 2021 at 15:58 | comment | added | Ilya Bogdanov | @PeterTaylor : Yes, I assume the graph is simple, and this seems to be a common trend nowadays, unless otherwise specified. I do not need connectedness; the second abstract just covers the non-connected case, as there will be more than one cycle. Starting from the next paragraph, I work under an (explicitly stated) assumption that $m\geq3$. This being assumed, I get that $nleq 2,$ since the newly constructed matching has precisely two edges in common with the third matching. Finally, the only graph on $2n\leq 4$ vertices having $\geq 3n$ edges is $K_4$... | |
| Jul 5, 2021 at 11:16 | comment | added | Peter Taylor | Separately, I think that the final line is misstated. Following the argument of the answer, I think it should say "Thus $2n \le 4$ or $m < 3$." But even then, I can't reconcile $2n \le 4$ with the claim (which I have verified) that $K_4$ is a solution for $m=3$. And, as a final observation, I think you may be assuming that the graph is simple. @MarioKrenn certainly seems to rely on this in referring to this answer, but with $n=2$ a non-simple loopless graph has a disjoint perfect matching per edge, and although any two of them form a Hamiltonian cycle, they don't generate a third. | |
| Jul 5, 2021 at 11:10 | comment | added | Peter Taylor | Rather late to nit-pick, but related questions which link to this one are attracting attention. There is an unstated assumption in this answer that the graph is connected: if that is not so, clearly there can be no Hamiltonian cycle, although equally the same argument can be applied separately to each connected component, and the existence of multiple perfect matchings in one connected component necessarily means that each edge in another connected component is in at least two perfect matchings of the whole graph. | |
| Dec 15, 2017 at 15:48 | comment | added | Mario Krenn | @Bogdanov - I want to say thank you again. Your answer has been used in a recent article in Physical Review Letters. I am citing this answere, see Reference [24]. Thanks! | |
| Aug 11, 2017 at 13:42 | history | bounty ended | Mario Krenn | ||
| Aug 11, 2017 at 13:13 | vote | accept | Mario Krenn | ||
| Aug 3, 2017 at 19:33 | vote | accept | Mario Krenn | ||
| Aug 7, 2017 at 18:30 | |||||
| Aug 3, 2017 at 19:07 | vote | accept | Mario Krenn | ||
| Aug 3, 2017 at 19:11 | |||||
| Apr 19, 2017 at 12:15 | vote | accept | Mario Krenn | ||
| Aug 3, 2017 at 19:07 | |||||
| Apr 13, 2017 at 9:18 | comment | added | Ilya Bogdanov | After ``untangling'' the picture with the first two matchings, you get a cycle of length 6 (it would be better to draw the correspoding untangled picture!). Each edge of the third matching is a chord in this cycle, so it splits the cycle into two arcs; I assume that each of them is subtended by this chord. The length of the arc is merely the number of edges in it. | |
| Apr 13, 2017 at 9:05 | comment | added | Mario Krenn | Ah I understand, you start with my conditions, sorry. In this example I have (in red) three disjoint perfect matchings (A,B,C), and they lead to D - they form three H. cycles: AB: ab-bf-fc-ce-ed-da; AC: af-fb-be-ec-cd-da; BC: ab-be-ed-dc-cf-fa. Could you please point to the case where some edges "subtends an arc of odd length" or "subtending minimal such arc". Sorry for these, for you certainly trivial, questions. I am excited by your answer, and looking forward to understand it :-) I am very thankful for your time and help! | |
| Apr 13, 2017 at 8:29 | comment | added | Ilya Bogdanov | 1) In your example two matchings share an edge (ad), which is prohibited by your conditions. If there is no common edge, the (necessarily even) cycles have lengths at least 4, and you may replace the edges of one matching belonging to one cycle by the edges of the other one. | |
| Apr 13, 2017 at 8:25 | comment | added | Mario Krenn | Thank you very much for your answer. Unfortunatly I can not follow some parts of the argument, and I would be grateful for a few more details: 1) "Two perfect matchings form a disjoint union of cycles." - Let's take the example here. There are two disjoint cycles (ad-da; be-ec-cf-fb), right? Then, what do you mean by "swap one of them"? Could you please point this out in my simple example? Thank you very much!! | |
| Apr 12, 2017 at 15:03 | history | answered | Ilya Bogdanov | CC BY-SA 3.0 |
