4
$\begingroup$

This is a question inspired by "A question about independent set in regular graphs".

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

Can any one prove or disprove the following:

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

We Know the following facts:

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

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

EDIT: Fact 3. There is a counterexample for the following claim:" Every nonempty regular simple graph contains two disjoint maximal independent sets".

$\endgroup$
  • $\begingroup$ It seems a nice question. $\endgroup$ – user42090 Dec 3 '13 at 3:54
  • 1
    $\begingroup$ @bof Check the reference for counterexample in this paper: renyi.hu/~p_erdos/1982-03.pdf $\endgroup$ – joro Dec 3 '13 at 7:12
  • $\begingroup$ I didn't wrote this is a counterexample to the question, just replied to a comment question of bof (now deleted). $\endgroup$ – joro Dec 4 '13 at 13:49
2
$\begingroup$

As Joro said, there is a counterexample for your question. In fact, C. Berge and C. Payan (independently) conjectured that any regular graph has two disjoint maximal independent sets of vertices, and this conjecture has shown to be false for some regular graphs. See the following papers:

  1. C. Payan, A counter-example to the conjecture: "Every nonempty regular simple graph contains two disjoint maximal independent sets", Graph Theory Newsletter 6 (1977) 7-8.

  2. C. Payan, Coverings by minimal transversals, Discrete Math. 23 (1978) 273-277.

Note that this conjecture has also positive answer in some classes of regular graphs!

$\endgroup$
  • 3
    $\begingroup$ This is not my answer! In my question $T$ is a maximal independent set in $G$, but $H$ is an independent dominating set for $T$. Note that there is a counterexample for the following claim:" Every nonempty regular simple graph contains two disjoint maximal independent sets". $\endgroup$ – Ali Dehghan Dec 3 '13 at 12:52
  • $\begingroup$ Joro's comment is a reply to a now-deleted comment, and it is about an assertion that is stronger than the one in the question. $\endgroup$ – S. Carnahan Dec 7 '13 at 13:17

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.