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

1. In the graph G choose two non-adjacent vertices $u$ and $v$ which have not yet been examined. If all pairs $(u,v)$ have been looked at then stop.
2. Create the graph $G^{\text{'}}$ by adding the edge $(u,v)$
3. If $\gamma \left(G^{\text{'}}\right)=\gamma \left(G\right)$ then $G\leftarrow G^{\text{'}}$ , otherwise return to 1 and pick another pair.

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.

Our contribution

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.

3-covers

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 ${\displaystyle 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.

Reformulation of the conjecture

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

Work towards a proof of the conjecture

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

Proposition 1:

$\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.