Written on the Wall II - Conjecture 327

Reference: E. DeLaVina, Written on the Wall II, Conjectures of Graffiti.pc

theorem WrittenOnTheWallII.GraphConjecture327.conjecture327 : False ↔ ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) [inst : DecidableRel G.Adj], G.Connected → 3 * G.dominationNumber = G.indepDominationNumber → G.IsWellTotallyDominated

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$:

1. Connected: Yes, path exists between any two vertices through $u$ and $v$.
2. Domination Number $\gamma(G)$: The set $\{u, v\}$ dominates all vertices. Since there is no universal vertex, $\gamma(G) = 2$.
3. 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$.
4. Condition: $3 \gamma(G) = 3 \times 2 = 6 = i(G)$. The condition holds.
5. 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.