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

Chang, Tony Yu; Clark, W. Edwin

J. Graph Theory 17, No. 1, 81-107 (1993).

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\).

Reviewer: B.Zelinka (Liberec)

MSC:

05C35	Extremal problems in graph theory
05C99	Graph theory

Keywords:

grid graph; dominating set; domination number

References:

[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)