The Domination Numbers of the 5 × n and 6 × n Grid Graphs

: The k \Theta n grid graph is the product P k \Theta P n of a path of length k \Gamma 1 and a path of length n \Gamma 1. We prove here formulas found by E. O. Hare for the domination numbers of P 5 \Theta P n and P 6 \Theta P n . 1 Introduction A dominating set in a graph G is a set S of vertices having the property that every vertex is either in S or adjacent to a vertex in S. The domination number fl(G) of G is the cardinality of a smallest dominating set in G. For an extensive survey of domination problems and a comprehensive bibliography we refer the reader to the recent survey volume edited by Hedetniemi and Laskar [5]. In this paper we establish the domination numbers fl k;n of the (complete) k \Theta n grid graphs for k = 5 and 6. Jacobson and Kinch [6] established fl k;n for k = 1, 2, 3 and 4. Beyond k = 4 the problem becomes much more difficult. E. O. Hare [3] developed an algorithm to compute fl k;n and using the output of an implementation of her algorithm she was able t..