WOWII Conjecture 327

Let G be a simple connected graph. If 3 · γ(G) = γ_i(G), then G is well totally dominated, where γ(G) is the domination number of G and γ_i(G) is the independent domination number of G.

Proof Sketch: The conjecture states that if $3\gamma(G) = i(G)$ for a connected graph $G$, then $G$ is well totally dominated. However, this conjecture is FALSE.

Counterexample: Consider a graph $G$ with 12 vertices: $u, v, a_0, a_1, a_2, a_3, a_4, b_0, b_1, b_2, b_3, b_4$. The edges are:

$(u, v)$

$(u, a_i)$ for all $i \in {0, 1, 2, 3, 4}$

$(v, b_i)$ for all $i \in {0, 1, 2, 3, 4}$

$(a_0, b_3), (a_1, b_3), (a_2, b_0), (a_3, b_0), (a_4, b_3), (a_4, b_4)$

Properties of $G$:

Connected: Yes, path exists between any two vertices through $u$ and $v$.

Domination Number $\gamma(G)$: The set ${u, v}$ dominates all vertices. Since there is no universal vertex, $\gamma(G) = 2$.

Independent Domination Number $i(G)$: The minimum independent dominating set has size 6 (e.g., ${u, b_0, b_1, b_2, b_3, b_4}$). Thus $i(G) = 6$.

Condition: $3 \gamma(G) = 3 \times 2 = 6 = i(G)$. The condition holds.

Well Totally Dominated: A graph is well totally dominated if all minimal total dominating sets have the same size.

${u, v}$ is a minimal total dominating set of size 2.

${v, b_0, b_3}$ is a minimal total dominating set of size 3. Since $2 \neq 3$, $G$ is NOT well totally dominated.

The counterexample has been found by Moritz Firsching and Goran Žužić using an experimental pipeline.