5.1 Vizing's conjecture and related graph properties  (Page 2/4)

Vizing's conjecture

Creating bounds for domination numbers is common practice since calculating a graphs domination number was proven NP-Complete by Garey and Johnson [link] in 1976. Arguably, the biggest open problem in Domination Theory is Vizing's Conjecture. It states that the product of the domination number of any two simple graphs $G$ and $H$ is no larger than the domination number of their cartesian product graph.

Clark and suen's proof

In 2000, Clark and Suen [link] proved that for any simple graphs G and H,

Their proof finds an upper and lower bound for the number of dominatiors in a Cartesian product, and combines the inqualities to put a bound on $\gamma (G\square H)$ . The proof is shown here:

Say that D is a dominating set of $G\square H$ . Let $\{u_1,...,u_{\gamma \left(G\right)}\}$ be a dominating set of $G$ . We can create partitions $\{{\Pi }_1,...,{\Pi }_{\gamma \left(G\right)}\}$ such that if $u\in {\Pi }_i$ , then $u=u_i$ or $u\in N\left(u_i\right)$ . Now we can create a partition of dominators $\{D_1,...,D_{\gamma \left(G\right)}\}$ , where

Let

Since $P_i\cup (V\left(H\right)-N_H\left[P_i\right])$ is a dominating set of $H$ for any $i$ , the number of vertices in $V\left(H\right)$ not dominated by $P_i$ satisfies

For $v\in V\left(H\right)$ , let

Also, let

Now, we want to find upper and lower bounds for $\left|C\right|$ . Let

We then see that:

Note that if $v\in V\left(H\right)-N_H\left[P_i\right]$ , then the vertices in ${\Pi }_i\times \left\{v\right\}$ must be dominated by vertices in $Q_v$ , so $(i,v)\in L_i$ . This implies that

So,

For each $v\in V\left(H\right),|R_v|\le |Q_v|$ . If not, $\{u:(u,v)\in Q_v\}\cup \{u_j:(j,v)\notin R_v\}$ is a dominating set in G with cardinality

which is a contradiction. Then

It then follows that $\gamma \left(G\right)\gamma \left(H\right)-\left|D\right|\le \left|C\right|\le \left|D\right|$ , which concludes the theorem. $\square$

Proofs for specific cases of $\gamma \left(G\right)$

Additionally, the proofs that Vizing's conjecture holds for $\gamma \left(G\right)=1$ and $\gamma \left(G\right)=2$ are trivial. In 2004, Sun [link] proved that Vizing's conjecture holds for $\gamma \left(G\right)=3$ . We will briefly step through the main ideas behind the proof here.

The idea behind the proof is that we can count three disjoint sets of dominators in $G\square H$ , such that each of these sets has cardinality of at least $\gamma \left(H\right)$ . Since the sets are disjoint, the number of dominators in $G\square H$ must be at least the sum of the cardinalities of these sets, namely $3\gamma \left(H\right)=\gamma \left(G\right)\gamma \left(H\right)$ . First, we assume that $G$ is 3-critical. This generalizes for all graphs with $\gamma \left(G\right)=3$ , by a bit of reasoning we will go through next. Without loss of generality, we can call the dominators of $G\{1,p,q\}$ , with $1=V\left(G\right)-N\left[p\right]\cup N\left[q\right]$ . A set with this property always exists in a 3-critical graph. Obviously 1 is adjacent to neither $p$ nor $q$ , but the proof must check the cases in which $p$ and $q$ are adjacent to each other and the case in which they are not. It uses these cases to build the appropriate subcases, and some of the math can be cumbersome and difficult to follow.

The step to k-critical

This assumption is key to Sun's proof, but how does she justify this assumption? The k-critical assumption comes from a familiar trick that has been used in proofs for many simple inequalities including the AM-GM inequality. We start by generating an algorithm to raise or lower one side of the inequality while leaving the other unchanged. In the K-critical assumption we want to keep both $\gamma \left(G\right)$ and $\gamma \left(H\right)$ unchanged while lowering $\gamma (G\square H)$ . So the algorithm works as follows: