2011/09/04 by Elliot Krop, Krop, Elliot
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1109.0707
This paper has been withdrawn by the author due to a problem with the "label exchange"
arxiv created 2011/09/16 · arxiv updated 2011/09/19
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 prove the conjecture.