[VIZING’S CONJECTURE: A SURVEY AND RECENT RESULTS (2009) by Bostjan Bresar , Paul Dorbec , Wayne Goddard , Bert L. Hartnell , Michael A. Henning , Sandi Klavzar , Douglas F. Rall](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.159.7029) p.25:



> 
> Conjecture 9.6. For all graphs $G$ and $H$,
>  $$\gamma(G \square H) \ge \min\{i(G)\gamma(H), i(H)\gamma(G)\}$$
> 
> 
> 


where $\square$ is the cartesian product of graphs and $i(G)$ is the independent domination number.


For cartesian squares it is $$\gamma(G \square G) \ge \gamma(G) i(G)$$


According to sage and my verification square of the graph on 7 vertices $[0 \ldots 6]$ with edges
$$[(0, 4), (0, 5), (0, 6), (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6)]$$
appears a counterexample to Conjecture 9.6 (note that vertex 3 is disconnected).


Computation:



```
sage: G=Graph(':Fo@I@I@J') #from sparse6
sage: Gs=G.cartesian_product(G)
sage: (Gs.dominating_set(value_only=True),G.dominating_set(value_only=True),G.dominating_set(value_only=True,independent=True) )
(11, 3, 4)

```

Verification:


Since the order is only $7$, $\gamma(G)=3$ and $i(G)=4$ were verified by enumerating
all subsets of the vertices. For $\gamma(G \square G)=11$ the dominating set returned by sage
was verified and it is an upper bound for the correct value.


I well might have misunderstood the conjecture.



> 
> Is the above graph a counterexample of Conjecture 9.6?
> 
> 
> 


Adding disconnected vertices to $G$ gives more counterexamples.



Is this a counterexample to a conjecture about independent domination in cartesian graph products?
To summarize a bit:


* $\gamma(G)$ is defined as the usual [domination number](http://mathworld.wolfram.com/DominatingSet.html%20) of a graph $G$
* $i(G)$ is defined as the smallest cardinality of a dominating set that is also an independent set


Your graph $C$ is the disjoint union of $K\_{3,3}$ and $K\_1.$


Clearly $\gamma(C) = 3$ and $i(C) = 4.$ For disjoint graphs $G,H$ we have $$(G \cup H) \square (G \cup H) = (G \square G) \cup (G \square H) \cup (H \square G) \cup (H \square H)$$


which gives for $C = K\_{3,3} \cup K\_1$


$$ C \square C = K\_{3,3} \square K\_{3,3} \cup K\_{3,3} \cup K\_{3,3} \cup K\_1.$$


And thus $$\gamma(C \square C) = \gamma(K\_{3,3} \square K\_{3,3}) + 2\gamma(K\_{3,3})+\gamma(K\_1) = 11.$$


This would indeed imply that $\gamma(C \square C) = 11 < \gamma(C)i(C) = 12.$ Making the conjecture false for disconnected graphs. 


**Edit**. In this [paper](http://www.sciencedirect.com/science/article/pii/S0166218X12002466#br000020) the authors construct an infinite family of graphs that are a counterexample to the claim of conjecture 9.6. The constructed family of graphs is disconnected but they remark it can be made connected. 


