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 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).


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)


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.

  • $\begingroup$ What is $\gamma(G)$? $\endgroup$ – Ketil Tveiten Sep 25 '12 at 11:28
  • $\begingroup$ @Ketil $\gamma(G)$ is the domination number, p. 1 from the paper: "As usual, γ stands for the domination number" $\endgroup$ – joro Sep 25 '12 at 11:43
  • 1
    $\begingroup$ maybe the original conjecture requires connected graphs? $\endgroup$ – Suvrit Sep 25 '12 at 12:29
  • $\begingroup$ @Suvrit don't know, just cited the conjecture and it says "for all graphs" $\endgroup$ – joro Sep 25 '12 at 12:42
  • $\begingroup$ @joro: I guess then you have uncovered a weakness in the conjecture! $\endgroup$ – Suvrit Sep 25 '12 at 13:51

To summarize a bit:

  • $\gamma(G)$ is defined as the usual domination number 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 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.

  • $\begingroup$ Thank you. What software are you using for computations? Sage's domination computations is slow for 8 X 8 products, haven't finished it yet for order 8. $\endgroup$ – joro Sep 25 '12 at 13:44
  • $\begingroup$ I am also using sage! $\endgroup$ – Jernej Sep 25 '12 at 13:45
  • $\begingroup$ Thank you Jernej! Will check up tomorrow. I am doing G.dominating_set() which invokes the GLPK solver on sage 5.3 on linux. Even if your machine is several times faster this seems strange to me... $\endgroup$ – joro Sep 25 '12 at 14:04
  • $\begingroup$ Are you also using nauty to generate connected graphs? $\endgroup$ – Jernej Sep 25 '12 at 14:11
  • $\begingroup$ @Jernej, yes I usually use nauty - it is quite faster than sage's for g in graphs(7): $\endgroup$ – joro Sep 25 '12 at 14:27

Since commenters asked about a connected counterexample, here is the connected counter example from the paper Jernej mentions.

p. 2. A $k$-leaf star is a central vertex with $k$ vertices connected to it. A $2k$-leaf-two star is a graph from two $k$-leaf stars with their central vertices connected by an edge. Define $G_k$ as the disjoint union of $2k^2$-leaf-two star and $k$ $K_2$s. $\gamma(G_k)=k+2$ and $i(G_k)=k^2+k+1$.

The disconnected counterexample is $F = G_k \square G_k$ with given dominating set $\gamma(F) \le 12k^2+8k+4$.

To make connected counterexample $G_k'$, add root vertex $r$ to $G_k$, connect it to one center of the two star and one vertex of each $K_2$.

$\gamma(G_k' \square G_k') \le 16k^2+12k+9$.

Because of the constants the smallest disconnected counterexample guaranteed by the construction is on $266$ vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.