Domination Numbers in Cartesian Products of Graphs

Abstract

The domination number of graphs represents the minimum cardinality of a dominating set, a fundamental concept in graph theory with applications in network design, facility location, and computational complexity. This paper examines domination numbers in Cartesian products of graphs, focusing on theoretical bounds, computational methods, and structural properties. We review key results including Vizing's conjecture, present established theorems regarding products of paths and cycles, and analyze the relationship between domination in factor graphs and their Cartesian products. Through rigorous mathematical analysis and illustrative examples, we demonstrate how product graph structures influence domination parameters and discuss implications for both theoretical graph theory and practical applications in network optimization.