<< Chapter < Page | Chapter >> Page > |
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.
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 $
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.
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:
Notification Switch
Would you like to follow the 'The art of the pfug' conversation and receive update notifications?