6
$\begingroup$

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

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ What is $\gamma(G)$? $\endgroup$
    – Ketil Tveiten
    Sep 25, 2012 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, 2012 at 11:43
  • 1
    $\begingroup$ maybe the original conjecture requires connected graphs? $\endgroup$
    – Suvrit
    Sep 25, 2012 at 12:29
  • $\begingroup$ @Suvrit don't know, just cited the conjecture and it says "for all graphs" $\endgroup$
    – joro
    Sep 25, 2012 at 12:42
  • $\begingroup$ @joro: I guess then you have uncovered a weakness in the conjecture! $\endgroup$
    – Suvrit
    Sep 25, 2012 at 13:51

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\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, 2012 at 13:44
  • $\begingroup$ I am also using sage! $\endgroup$
    – Jernej
    Sep 25, 2012 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, 2012 at 14:04
  • $\begingroup$ Are you also using nauty to generate connected graphs? $\endgroup$
    – Jernej
    Sep 25, 2012 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, 2012 at 14:27
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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