Timeline for Vertex cover of regular graph
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 21, 2016 at 7:52 | vote | accept | CommunityBot | ||
| Feb 21, 2016 at 4:21 | answer | added | Brendan McKay | timeline score: 3 | |
| Feb 21, 2016 at 4:13 | history | edited | user76479 | CC BY-SA 3.0 |
added 115 characters in body
|
| Feb 21, 2016 at 4:11 | comment | added | user76479 | @BrendanMcKay Could you post a full-fledged solution? | |
| Feb 21, 2016 at 4:10 | comment | added | Brendan McKay | More generally, the complement of $S$ is an independent set and the converse holds too. So finding a minimum $S$ is the same problem as finding a maximum independent set. Note that an $r$-regular non-complete graph has an independent set of size at least $n/r$. | |
| Feb 21, 2016 at 3:06 | comment | added | user76479 | @BrendanMcKay From your argument it seems like if we have $k$-partite graph we should have $|S|\leq\frac nc$ with $c\geq{1-\frac1k}$. | |
| Feb 21, 2016 at 2:57 | history | edited | user76479 | CC BY-SA 3.0 |
deleted 8 characters in body
|
| Feb 21, 2016 at 2:47 | comment | added | Brendan McKay | No. Consider if $G$ has a perfect matching (eg if it is bipartite). At least one end of each edge of the matching must be in $S$, so $|S|\ge n/2$. | |
| Feb 21, 2016 at 2:36 | history | edited | user76479 | CC BY-SA 3.0 |
added 230 characters in body; edited tags
|
| Feb 21, 2016 at 2:29 | history | asked | user76479 | CC BY-SA 3.0 |