2025/01/31 by J. Lee, Lee, Jia-Ying, Chia-An Liu +1
Computer Science · #05C69 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2502.00134
openalex publication_date 2025/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For positive integers m and n, the grid graph Gm,n is the Cartesian product of the path graph Pm on m vertices and the path graph Pn on n vertices. An integer \2\-dominating function of a graph is a mapping from the vertex set to \0,1,2\ such that the sum of the mapped values of each vertex and its neighbors is at least 2; the integer \2\-domination number of a graph is defined to be the minimum sum of mapped values of all vertices among all integer \2\-dominating functions. In this paper, we compute the integer \2\-domination numbers of G1,n and G2,n, attain an upper bound to the integer \2\-domination numbers of G3,n, and propose an algorithm to count the integer \2\-domination numbers of Gm,n for arbitrary m and n. As a future work, we list the integer \2\-domination numbers of G4,n for small n, and conjecture on its formula.