<< Chapter < Page | Chapter >> Page > |
It is obvious that after completing the algorithm the graph ${G}^{\text{'}}$ will have the same domination number as $G$ . Next it should be apparent that for any graph $H$ if $D$ dominates $G\square H$ then $D$ dominates ${G}^{\text{'}}\square H$ since ${G}^{\text{'}}\square H$ is just $G\square H$ with extra edges, i.e. $\gamma ({G}^{\text{'}}\square H)\le \gamma (G\square H)$ . So if Vizing's Conjecture holds for the special case of k-critical then it holds for all graphs, and contrastingly, if there is a counterexample the smallest will be k-critical.
Sun's proof is cumbersome and broken into many cases, but there is potential to eliminate the case of $p$ and $q$ being adjacent if a certain conjecture from Sumner and Blitch [link] is true. Specifically Sumner and Blitch conjectured that in every k-critical graph $i\left(G\right)=\gamma \left(G\right)$ where $i\left(G\right)$ is the Independence Number. The conjecture has been disproven for $k\ge 4$ but remains open in the case $k=3$ [link] . We've put work into developing a counterexample or showing that none exist, in hopes of shortening Sun's proof. This is equivalent to saying in if $G$ is 3-critical, then the complement of $G$ must have a ${K}_{3}$ subgraph which is not contained in a ${K}_{4}$ subgraph.
We call a graph $G$ a k-cover if for every k-1-tuple of vertices $({v}_{1},...,{v}_{k-1})$ there exists a vertex $w$ such that $w\in \bigcap _{i=1}^{k-1}N\left({v}_{i}\right)$ . K-covers are complements to graphs with domination number k, and specifically we're interested in 3-covers. So to add in the idea of the complement of a k-critical graph, we have come up with the idea of a minimal 3-cover. We call a 3-cover minimal if for every edge $(u,v)\in E$ there exists $w\in V$ and a choice of labels $a,b\in (u,v)$ s.t. $N\left(a\right)\cap N\left(w\right)=b$ . The relation between a domination 3 graphs and the minimality of their complement is that a graph $G$ is a 3-edge-critical graph if and only if $\overline{G}$ is a minimal 3-cover.
We can reformulate the original conjecture in a more constructuve form using 3-covers. An equivalent form is that there is no minimal 3-cover in which every ${K}_{3}$ is contained in a ${K}_{4}$ .
Starting by describing the set of counterexamples to the conjecture, we will want to show either that the set is empty, or produce an element from the set to disprove the conjecture. Consider graphs $G(V,E)$ from the set
$\delta \left(G\right)\ge 3$ .
Proof: Since $G$ has the property of being a minimal 3-cover if follows that $G$ is connected, and so each vertex $v$ has $deg\left(v\right)\ge 1$ . Since $G$ is a 3-cover, each edge is contained in a triangle, otherwise there would be a pair which has no common neighbors (the endpoints of any edge not in a triangle). This means any vertex containing an edge also belongs to a triple inducing a ${K}_{3}$ . By the last property of $G$ we have that each of these triples can be extended to a 4-tuple which induces a ${K}_{4}$ . Since each vertex is inside of such a 4-tuple, it follows that each vertex has degree at least 3.
Notification Switch
Would you like to follow the 'The art of the pfug' conversation and receive update notifications?