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.

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

2 Answers 2

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.

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .