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

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