2014/10/15 by Armando Grez, Grez, Armando, Michael Farina +1
Computer Science · #05C12 #05C30 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1410.4149
openalex publication_date 2014/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In his 1992 Ph.D. thesis Chang identified an efficient way to dominate m × n grid graphs and conjectured that his construction gives the most efficient dominating sets for relatively large grids. In 2011 Gonçalves, Pinlou, Rao, and Thomassé proved Chang's conjecture, establishing a closed formula for the domination number of a grid. In March 2013 Fata, Smith and Sundaram established upper bounds for the k-distance domination numbers of grid graphs by generalizing Chang's construction of dominating sets to k-distance dominating sets. In this paper we improve the upper bounds established by Fata, Smith, and Sundaram for the k-distance domination numbers of grids.