Skip to main content
1 of 3
Ali Dehghan
  • 385
  • 1
  • 12

A question about independent set in regular graphs

Suppose that $G$ is a simple $r$-regular graph. 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)$?

Ali Dehghan
  • 385
  • 1
  • 12