<p>The problem is that you confused the definiton in the paper of Aharoni &amp; Szabo and the normally used definition for the term "independence domination number". The former one refers to the largest size over all minimum set <strong>dominating an independent set</strong>, and the latter one is the smallest size of <strong>a dominating set which is also an independent set</strong>.</p>

<p>These two definitions are quite different, and as you noticed they have different symbols: $\gamma^i(G)$ and $i(G)$. The Theorem 1.1 you mentioned actually claims $\gamma(G)=\gamma^i(G)$ for chordal graphs $G$, and generally they are not equal to $i(G)$ even when $G$ is chordal. The following graph is a counterexample:</p>

<p><img src="https://i.sstatic.net/9XXWN.png" alt="example"></p>

<p>where $\gamma(G)=2$ and $i(G)=3$.</p>

<p>As a comment, Allan &amp; Laskar showed that $\gamma(G)=i(G)$ when $G$ is <a href="http://en.wikipedia.org/wiki/Claw-free_graph" rel="nofollow noreferrer">claw-free</a>, but there are no such conclusions for chordal graphs.</p>

CC BY-SA 3.0
2015-03-12T11:28:59.717Z
Thanks, indeed there are counterexamples to gamma(G)=i(G) for chordal.
joro
CC BY-SA 3.0
2015-03-12T22:37:44.550Z
So, just to be clear, we're saying that `Theorem 1.1` in OP's question is wrong, right? @WillardZahn
Millie Smith
CC BY-SA 3.0
2015-03-13T01:48:19.323Z
@MillieSmith The paper in the link only claims $\gamma(G)=\gamma^i(G)$, and the one in question is indeed wrong.
Wei Zhan
CC BY-SA 3.0
2015-03-12T11:14:26.357Z
2015-03-12T11:14:26.357Z
Wei Zhan
<p>Several papers appear to imply P=NP via chordal graphs, 
which suggests something is wrong.</p>

<p>As usual $\gamma(G)$ is the domination number and $i(G)$ and $\gamma^i(G)$
are the independence domination number.</p>

<p>According to <a href="http://page.mi.fu-berlin.de/szabo/PS/vizing.ps">VIZING’S CONJECTURE FOR CHORDAL GRAPHS, p.1</a></p>

<blockquote>
  <p>Theorem 1.1. [2] In chordal graphs $\gamma(G)=\gamma^i(G)=i(G)$.</p>
</blockquote>

<p>According to <a href="http://graphclasses.org/classes/gc_32.html">graphclasses.org</a></p>

<p>and a <a href="http://thomas-szymczak.de/dissertation.pdf">paper p. 55 of the document and 65 of the pdf</a>:</p>

<blockquote>
  <p>In chordal graphs Domination is NP-complete and Independent Domination is
  polynomial.</p>
</blockquote>

<p>The equality in Theorem 1.1 appears to imply P=NP since we can compute
$\gamma(G)=i(G)$ in chordal graphs by the above result.</p>

<blockquote>
  <p>What is wrong with this?</p>
</blockquote>

<cc.complexity-theory><graph-theory>
Several papers appear to imply P=NP via chordal graphs, what is wrong?
joro
# Several papers appear to imply P=NP via chordal graphs, what is wrong?

(Asked by: username_0 on 2015-03-12)

Several papers appear to imply P=NP via chordal graphs,
which suggests something is wrong.

As usual $\gamma(G)$ is the domination number and $i(G)$ and $\gamma^i(G)$
are the independence domination number.

According to [VIZING’S CONJECTURE FOR CHORDAL GRAPHS, p.1](http://page.mi.fu-berlin.de/szabo/PS/vizing.ps)

> Theorem 1.1. [2] In chordal graphs $\gamma(G)=\gamma^i(G)=i(G)$.

According to [graphclasses.org](http://graphclasses.org/classes/gc_32.html)

and a [paper p. 55 of the document and 65 of the pdf](http://thomas-szymczak.de/dissertation.pdf):

> In chordal graphs Domination is NP-complete and Independent Domination is
> polynomial.

The equality in Theorem 1.1 appears to imply P=NP since we can compute
$\gamma(G)=i(G)$ in chordal graphs by the above result.

> What is wrong with this?

**Tags:** cc.complexity-theory, graph-theory

---

## 1 answers

### Answer by username_1 on 2015-03-12. Score: 16 | Accepted answer

The problem is that you confused the definiton in the paper of Aharoni & Szabo and the normally used definition for the term "independence domination number". The former one refers to the largest size over all minimum set **dominating an independent set**, and the latter one is the smallest size of **a dominating set which is also an independent set**.

These two definitions are quite different, and as you noticed they have different symbols: $\gamma^i(G)$ and $i(G)$. The Theorem 1.1 you mentioned actually claims $\gamma(G)=\gamma^i(G)$ for chordal graphs $G$, and generally they are not equal to $i(G)$ even when $G$ is chordal. The following graph is a counterexample:

![example](https://i.sstatic.net/9XXWN.png)

where $\gamma(G)=2$ and $i(G)=3$.

As a comment, Allan & Laskar showed that $\gamma(G)=i(G)$ when $G$ is [claw-free](http://en.wikipedia.org/wiki/Claw-free_graph), but there are no such conclusions for chordal graphs.

> **Comments:**
> **username_0**: Thanks, indeed there are counterexamples to gamma(G)=i(G) for chordal.  
> **username_2**: So, just to be clear, we're saying that `Theorem 1.1` in OP's question is wrong, right? @WillardZahn  
> **username_1**: @MillieSmith The paper in the link only claims $\gamma(G)=\gamma^i(G)$, and the one in question is indeed wrong.  

---

