加载中…
For any graph , a subset \emph{dominates} if all vertices are contained in the closed neighborhood of , that is . The minimum cardinality over all such is called the domination number, written . In 1963, V.G. Vizing conjectured that $\gamma(G \square H) \geq \gamma(G)\gamma(H)\square$ stands for the Cartesian product of graphs. In this note, we define classes of graphs , for , so that every graph belongs to some such class, and corresponds to class of Bartsalkin and German. We prove that for any graph in class , $\gamma(G\square H)\geq \left(\gamma(G)-\sqrt{\gamma(G)}\right)\gamma(H)$.

生成讲解博客的中文版本

生成AI智能校验的中文版本