The domination numbers of the 5\({\times} n\) and 6\({\times} n\) grid graphs. (English) Zbl 0780.05030

The \(k\times n\) grid graph is the Cartesian product \(P_ k\times P_ n\), where \(P_ k\), \(P_ n\) denote the paths of lengths \(k-1\), \(n-1\) respectively. A dominating set in a graph \(G\) is a subset \(D\) of the vertex set \(V(G)\) of \(G\) such that for each \(x\in V(G)-D\) there exists a vertex \(y\in D\) adjacent to \(x\). The domination number of a graph is the minimum number of vertices of a dominating set in that graph. The domination number of the \(k\times n\) grid graph is denoted by \(\gamma_{k,n}\). E. O. Hare has developed an algorithm for computing it. She conjectured that certain formulae hold for \(\gamma_{5,n}\) and \(\gamma_{6,n}\) for all \(n\) and verified this for \(n\leq 500\). The authors of the present paper prove these formulae for all \(n\).


05C35 Extremal problems in graph theory
05C99 Graph theory
Full Text: DOI


[1] , and , Domination numbers of complete grid graphs, I. Ars Combinat. To appear.
[2] Cockayne, Congress. Numer. 47 pp 217– (1985)
[3] Algorithms for grid and grid-like graphs. Ph. D. thesis, Department of Computer Science, Clemson University, Clemson, SC (1989).
[4] Hare, Congress. Numer. 55 pp 81– (1986)
[5] Hedetniemi, Discrete Math. 86 pp 1– (1990)
[6] Jacobson, Ars Combinat. 18 pp 33– (1983)
[7] Singh, Congress. Numer. 59 pp 297– (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.