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

Improve this question
$\endgroup$
2
  • $\begingroup$ $G$ has $n$ vertices. $\endgroup$ Commented Nov 29, 2013 at 6:51
  • $\begingroup$ What is an independent set $H$ for $T$? $\endgroup$ Commented Nov 29, 2013 at 22:04

1 Answer 1

Reset to default
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$.

Improve this answer
$\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$ Commented Dec 2, 2013 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$ Commented Dec 2, 2013 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$ Commented Dec 2, 2013 at 9:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.