Skip to main content
MathOverflow

Return to Question

added 147 characters in body
Source Link
Ali Dehghan
Ali Dehghan
  • 385
  • 1
  • 12

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

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

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

added 18 characters in body
Source Link
Ali Dehghan
Ali Dehghan
  • 385
  • 1
  • 12

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

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

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

Source Link
Ali Dehghan
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)$?