Domination Numbers of Complete Grid Graphs, \(I\)

Tony Yu Chang1, W.Edwin Clark1, Eleanor O.Hare2
1Department of Mathematics, University of South Florida, Tampa, Florida 33620-5700, USA
2 Department of Computer Science, Clemson University, Clemson, South Carolina 29634-1906, USA

Abstract

This paper concerns the domination numbers \(\gamma_{k,n}\) for the complete \(k \times n\) grid graphs for \(1 \leq k \leq 10\) and \(n \geq 1\). These numbers were previously established for \(1 \leq k \leq 4\). Here we present dominating sets for \(5 \leq k \leq 10\) and \(n \geq 1\). This gives upper bounds for \(\gamma_{k,n}\) for \(k\) in this range. We discuss evidence that indicates that these upper bounds are also lower bounds.