2015/02/03 by Aziz Contractor, Elliot Krop, Contractor, Aziz +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1502.00708
5 pages
arxiv created 2015/02/03 · openalex publication_date 2015/02/03 · arxiv updated 2015/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 that if |G|≥ γ(G)γ(H) and |H|≥ γ(G)γ(H), then the conjecture holds. This result quickly implies Vizing's conjecture for almost all pairs of graphs G,H with |G|≥ |H|, satisfying |G|≤ q(|H|)/(logq|H|) for q=(1)/(1-p) and p the edge probability of the Erdős-Rényi random graph.