A question about independent set in regular graphs

Question

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)$.

It is easy to see that if $T$ is an independent set for $G$, then there exists an independent dominating set $H$ for $T$ such that $| T \cap H |=O(\log n)$.

Question: Suppose that $G$ is an $r$-regular graph with $r\neq 0$. If $T$ is an independent set for $G$, does there exist an independent dominating set $H$ for $T$ such that $T \cap H =\emptyset$?

If the answer to Question is no, does there exist an independent dominating set $H$ for $T$ such that $| T \cap H | =O(\log\log n)$?

Answer 1

Clearly, if $G$ is $1$-regular or $2$-regular, and if $T$ is an independent set in $G$, then there is a maximal independent set $H$ in $G$ such that $T\cap H=\emptyset$.

Let $G$ be the $3$-regular graph of order $14$ with $V(G)=\{a,b,c,d,e,f,g,t,u,v,w,x,y,z\}$ and $E(G)=\{ab,bc,cd,de,ea,fb,fd,gc,ge,fg,tu,uv,vw,wx,xt,yu,yw,zx,zv,yz,at\}$.

Then $T=\{b,e,u,x\}$ is a maximal independent set in $G$, and if $H$ is any independent set in $G$ which is dominating for $T$, then $T\cap H\ne\emptyset$.

If $m\in\mathbb N$ then $mG$ is a $3$-regular graph of order $n=14m$ containing a maximal independent set $T'$ (with $|T'|=4m$) such that, if $H$ is any independent set in $mG$ which is dominating for $T'$, then $|T'\cap H|\ge m=\frac1{14}n$. This contradicts your "easy to see" claim about $|T\cap H|=O(\log n)$.

P.S. No doubt some assumption was omitted from the question. Connectedness is not enough, as the following construction shows.

Theorem. 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$.

Proof. Take $6m$ vertices $a_0,\ a_1,\ a_2,\dots,a_{6m-1}$ and join them cyclically with edges $a_0a_1,\ a_1a_2,\dots,a_{6m-1}a_0$.

For each $j\in\{0,1,2,\dots,6m-1\}$, add vertices $x_j,\ y_j,\ z_j,\ t_j,\ u_j,\ v_j,\ w_j$ and edges $x_jy_j,\ x_jz_j,\ y_jt_j,\ y_ju_j,\ z_jv_j,\ z_jw_j,\ t_jv_j,\ t_jw_j,\ u_jv_j,\ u_jw_j$.

For each $j\in\{0,1,2,\dots,6m-1\}\setminus\{1,4,7,\dots,6m-2\}$, add an edge $a_jx_j$.

For each $j\in\{1,4,7,\dots,6m-2\}$, add a vertex $b_j$ and edges $a_jb_j,\ b_jx_j$.

Finally, join the vertices $b_j$ in pairs with edges $b_1b_{3m+1},\ b_4b_{3m+4},\dots,b_{3m-2}b_{6m-2}$.

Now $T=\{a_j:j=1,4,7,\dots,6m-2\}\cup\{y_j:j=0,1,2,\dots,6m-1\}\cup\{z_j:j=0,1,2,\dots,6m-1\}$ is a maximal independent set. If $H$ is any independent set which is dominating for $T$, then for each $j\in\{1,4,7,\dots,6m-2\},\ H$ must contain at least one of the vertices $a_j,\ y_j,\ z_j,\ y_{j-1},\ z_{j-1},\ y_{j+1},\ z_{j+1}$, whence $|T\cap H|\ge2m$.