# A new question about maximal independent sets in regular graphs

This is a question inspired by "A question about independent set in regular graphs".

Suppose that $G$ is a simple $r$-regular graph with $n$ vertices. We say $H$ is a dominating set for $T$, if for every vertex $v\in T$, we have $v\in H$ or there is a vertex $u\in H$ such that $vu\in E(G)$.

Can any one prove or disprove the following:

Question 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$?

We Know the following facts:

Fact 1. 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$.

Fact 2. For each $m\in\mathbb N$ there is a connected cubic graph $G=(V,E)$ of order $|V|=n=50m$, and there is a maximal independent set $T\subseteq V$, with $|T|=14m$, such that, for any independent set $H\subseteq V$ which is dominating for $T$, we have $|T\cap H|\ge2m=\dfrac1{25}n$.

EDIT: Fact 3. There is a counterexample for the following claim:" Every nonempty regular simple graph contains two disjoint maximal independent sets".

• It seems a nice question. – user42090 Dec 3 '13 at 3:54
• @bof Check the reference for counterexample in this paper: renyi.hu/~p_erdos/1982-03.pdf – joro Dec 3 '13 at 7:12
• I didn't wrote this is a counterexample to the question, just replied to a comment question of bof (now deleted). – joro Dec 4 '13 at 13:49

• This is not my answer! In my question $T$ is a maximal independent set in $G$, but $H$ is an independent dominating set for $T$. Note that there is a counterexample for the following claim:" Every nonempty regular simple graph contains two disjoint maximal independent sets". – Ali Dehghan Dec 3 '13 at 12:52