Skip to main content
1 of 4
bof
  • 15.1k
  • 2
  • 48
  • 72

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 seems to contradict your "easy to see" claim about $|T\cap H|=O(\log n)$.

Evidently I am missing something. Either I am writing nonsense, or I misunderstood the question, or perhaps you misstated it?

bof
  • 15.1k
  • 2
  • 48
  • 72