Timeline for A question about independent set in regular graphs
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2013 at 9:57 | comment | added | bof | You're welcome. I don't see why my answer shows that your bound is tight. For regular graphs you're saying that you can get $|T_1\cap T_2|\le\frac12|T_1|$? But my examples have $|T_1\cap T_2|/|T_1|=\frac14$ or $\frac17$? | |
| Dec 2, 2013 at 7:59 | comment | added | Ali Dehghan | Can you prove or disprove the following: Suppose that $G$ is an $r$-regular graph with $r\neq 0$. Is there a maximal independent set $T$ in $G$, such that there exists an independent dominating set $H$ for $T$ such that $T \cap H =\emptyset$? | |
| Dec 2, 2013 at 6:54 | comment | added | Ali Dehghan | This completely address my question. Thank you very much. About "It is easy to see that ... such that $| T \cap H |=O(\log n)$." I made a mistake. In fact, it is easy to see that if $G$ is a graph, $G\neq \overline{K_{n}}$ and $T_{1}$ is an independent set of $G$, then there exists $T_{2}$ such that, $T_{2}$ is an independent dominating set for $T_{1}$ and $ \vert T_{1} \cap T_{2}\vert \leq \frac{2\Delta(G) -\delta(G) }{2\Delta(G)} \vert T_{1}\vert$. It is shown by your answer that this bound is tight. | |
| Dec 2, 2013 at 5:21 | history | edited | bof | CC BY-SA 3.0 |
added 2 characters in body
|
| Dec 1, 2013 at 11:51 | history | edited | bof | CC BY-SA 3.0 |
spelling correction
|
| Dec 1, 2013 at 9:29 | vote | accept | Ali Dehghan | ||
| Dec 1, 2013 at 8:39 | vote | accept | Ali Dehghan | ||
| Dec 1, 2013 at 8:39 | |||||
| Dec 1, 2013 at 6:25 | history | edited | bof | CC BY-SA 3.0 |
added 1261 characters in body
|
| Nov 30, 2013 at 14:02 | history | answered | bof | CC BY-SA 3.0 |