GRAPH AND ITS COMPLEMENT

NEW

Problem: Reconstructed conjecture: for a finite simple graph $G$, let $\gamma(G)$ be its domination number. The “above inequality” is Vizing’s Nordhaus–Gaddum domination product inequality

Rao’s conjecture says that the only regular graphs attaining equality are

Here $L_2(3)$ is the $3\times3$ lattice/rook graph, and $G_0$ is the fixed exceptional graph denoted so in Rao’s paper.

Result: The conjecture is false as stated.

For any $m\ge2$, let

be the disjoint union of $m$ independent edges. Then $G$ is $1$-regular on $2m$ vertices. Each component $K_2$ requires one dominator, so

The complement $\overline G$ is the cocktail-party graph $K_{2m}$ with a perfect matching removed; it is $(2m-2)$-regular. It has no universal vertex, so $\gamma(\overline G)\ge2$. Any two vertices not paired in the removed matching dominate all vertices, hence

Therefore

so equality holds.

As $m$ varies, this gives infinitely many regular equality examples. Since Rao’s list contains only four fixed finite graphs, all sufficiently large $mK_2$ are not on the list. Thus the literal conjecture is disproved. The failure is caused by a missing connectedness/co-connectedness type hypothesis; merely excluding isolated vertices is not enough.

Citation: No external result is needed for the counterexample. The reconstructed inequality is the standard Vizing domination Nordhaus–Gaddum product inequality from V. G. Vizing, “Some unsolved problems in graph theory,” Russian Math. Surveys 23:6 (1968), 125–141.