In his 1992 Ph.D. thesis Chang identified an efficient way to dominate m-by-n grid graphs and conjectured that his construction gives the most efficient dominating sets for relatively large grids. In 2011 Goncalves, Pinlou, Rao, and Thomasse 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 use algebraic and geometric arguments to improve the upper bounds established by Fata, Smith, and Sundaram for the k-distance domination numbers of grids.
Erik Insko, Department of Mathematics, Florida Gulf Coast University
Farina, Michael and Grez, Armando
"New Upper Bounds on the Distance Domination Numbers of Grids,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 17
, Article 7.
Available at: http://scholar.rose-hulman.edu/rhumj/vol17/iss2/7