Timeline for Would a graph with such maximum weighted matchings exist?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 9, 2012 at 12:20 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 822 characters in body
|
| Nov 9, 2012 at 11:56 | comment | added | joro | Edited with edges, dumb me... | |
| Nov 9, 2012 at 11:51 | comment | added | Tony Huynh | No problem. In that case, the proof still answers your question since the degree 1 assumption implies that the distinguished edges are each at the end of a path component of $M_1 \triangle M_2$, which is all we need. | |
| Nov 9, 2012 at 11:45 | comment | added | joro | You are right, sorry. I screwed the question :-(. I meant to ask about distinguished edges with one vertex of degree $1$. Sorry again :( | |
| Nov 9, 2012 at 11:39 | comment | added | Tony Huynh | See my comment above. Your examples do not satisfy condition (1), since there cannot be a maximum weight matching which avoids $x,y,z$ for any choice of $x,y,z$. | |
| Nov 9, 2012 at 11:35 | comment | added | joro | $C_4$ (and $C_{2k}$) with weights 1 have exactly 2 maximum weighted matchings satisfying the question without deg. 1 restriction. | |
| Nov 9, 2012 at 11:35 | comment | added | Tony Huynh | If all weights are 1 and the graph has a perfect matching, then every maximum weight matching will be a perfect matching and hence cover $x,y,z$. So condition (1) will not be satisfied. Not relevant, but this proof also shows that the only graph with exactly two perfect matchings is an even cycle. | |
| Nov 9, 2012 at 11:27 | comment | added | joro | Thank you. Are you sure this works if x,y,z are not of degree 1? I think I found a lot of graphs with exactly 2 perfect matchings (weights 1) and the they satisfy my question except for degree 1? | |
| Nov 9, 2012 at 11:05 | history | undeleted | Tony Huynh | ||
| Nov 9, 2012 at 11:05 | history | deleted | Tony Huynh | ||
| Nov 9, 2012 at 11:04 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 70 characters in body
|
| Nov 9, 2012 at 10:59 | history | answered | Tony Huynh | CC BY-SA 3.0 |