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$
3
  • $\begingroup$ It seems a nice question. $\endgroup$
    – user42090
    Commented Dec 3, 2013 at 3:54
  • 1
    $\begingroup$ @bof Check the reference for counterexample in this paper: renyi.hu/~p_erdos/1982-03.pdf $\endgroup$
    – joro
    Commented Dec 3, 2013 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
    Commented Dec 4, 2013 at 13:49

1 Answer 1

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$
2
  • 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$ Commented Dec 3, 2013 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
    Commented Dec 7, 2013 at 13:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .