2011/09/09 by K. Choudhary, Keerti Choudhary, Choudhary, K. +6
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1109.2174
arxiv created 2011/09/09 · openalex publication_date 2011/09/09 · arxiv updated 2011/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A dominating set D for a graph G is a subset of V(G) such that any vertex not in D has at least one neighbor in D. The domination number γ(G) is the size of a minimum dominating set in G. Vizing's conjecture from 1968 states that for the Cartesian product of graphs G and H, γ(G) γ(H) ≤ γ(G \Box H), and Clark and Suen (2000) proved that γ(G) γ(H) ≤ 2γ(G \Box H). In this paper, we modify the approach of Clark and Suen to prove a variety of similar bounds related to total and paired domination, and also extend these bounds to the n-Cartesian product of graphs A1 through An.