# zbMATH — the first resource for mathematics

A class of graphs approaching Vizing’s conjecture. (English) Zbl 1416.05208
Summary: For any graph $$G=(V,E)$$, a subset $$S\subseteq V$$ 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)$$. V. G. Vizing [Vychisl. Sistemy, Novosibirsk 9, 30–43 (1963; Zbl 0194.25203)] 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 A. M. Bartsalkin and L. F. German [Izv. Akad. Nauk Mold. SSR, Ser. Fiz.-Tekh. Mat. Nauk 1979, No. 1, 5–8 (1979; Zbl 0457.05053)]. We prove that for any graph $$G$$ in class $$\mathcal{A}_1$$, $$\gamma(G\square H)\ge(\gamma(G)-\square{\gamma(G)})\gamma(H)$$.

##### MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C76 Graph operations (line graphs, products, etc.)
Full Text: