A class of graphs approaching Vizing's conjecture

Abstract

For any graph $G=(V,E)$, a subset $S\subseteq V$ \emph{dominates} $G$ if all vertices are contained in the closed neighborhood of $S$, that is $N[S]=V$. The minimum cardinality over all such $S$ is called the domination number, written $\gamma (G)$. In 1963, V.G. Vizing conjectured that $\gamma (G\square H)\ge \gamma (G)\gamma (H)$ where $\square$ stands for the Cartesian product of graphs. In this note, we define classes of graphs ${\mathcal{A}}_n$, for $n\ge 0$, so that every graph belongs to some such class, and ${\mathcal{A}}_0$ corresponds to class $A$ of Bartsalkin and German. We prove that for any graph $G$ in class ${\mathcal{A}}_1$, $\gamma (G\square H)\ge \left(\gamma (G)-\sqrt{\gamma (G)}\right)\gamma (H)$.

arXiv comment7 pages in Theory and Applications of Graphs: Vol. 3: Iss. 1, Article 4 (2016)