-1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ $G$ has $n$ vertices. $\endgroup$ Nov 29 '13 at 6:51
  • $\begingroup$ What is an independent set $H$ for $T$? $\endgroup$
    – hbm
    Nov 29 '13 at 22:04
4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Dec 2 '13 at 6:54
  • $\begingroup$ 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$? $\endgroup$ Dec 2 '13 at 7:59
  • 1
    $\begingroup$ 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$? $\endgroup$
    – bof
    Dec 2 '13 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.