2015/12/03 by Aziz Contractor, Elliot Krop, Contractor, Aziz +1
Mathematics · #05C69 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C69
paper · pdf · doi:10.48550/arxiv.1512.01077
7 pages in Theory and Applications of Graphs: Vol. 3: Iss. 1, Article 4 (2016)
arxiv created 2016/04/04 · arxiv updated 2016/04/06
For any graph G=(V,E), a subset S⊆ 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 γ(G). In 1963, V.G. Vizing conjectured that γ(G \square H) ≥ γ(G)γ(H) where \square stands for the Cartesian product of graphs. In this note, we define classes of graphs An, for n≥ 0, so that every graph belongs to some such class, and A0 corresponds to class A of Bartsalkin and German. We prove that for any graph G in class A1, γ(G\square H)≥ (γ(G)-√(γ(G)))γ(H).