×

Chessboard domination problems. (English) Zbl 0818.05057

The classical problems of covering chessboards with the minimum number of chess pieces were important in motivating the revival of the study of dominating sets in graphs, which commenced in the early 1970’s. These problems certainly date back to de Jaenisch and have been mentioned in the literature frequently since that time.
A graph \(P_ n\) may be formed from an \(n\times n\) chessboard and a chess piece \(P\) by taking the \(n^ 2\) squares of the board as vertices and two vertices are adjacent if piece \(P\) situated at one of the squares is able to move directly to the other. For example the Queen’s graph \(Q_ n\) has the \(n^ 2\) squares as vertices and squares are adjacent if they are on the same line (row, column or diagonal).
In this paper we survey recent results which involve various domination parameters for graphs which are constructed in this way. Outlines of some of the proofs are given, although most appear elsewhere.

MSC:

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

References:

[1] Behrend, F. A., On sets of integers which contain no 3 terms in arithmetic progression, Proc. Nat. Acad. Sci. U.S.A., 32, 331-332 (1946) · Zbl 0060.10302
[2] Berge, C., Theory of Graphs and its Applications, ((1962), Methuen: Methuen London), 40-51
[3] E.J. Cockayne, B. Gamble and B. Shepherd, Domination of chessboards by queens on a column, Ars. Combin., to appear.; E.J. Cockayne, B. Gamble and B. Shepherd, Domination of chessboards by queens on a column, Ars. Combin., to appear. · Zbl 0583.05005
[4] E.J. Cockayne, B. Gamble and B. Shepherd, Domination parameters for the bishops graph, Discrete Math., to appear.; E.J. Cockayne, B. Gamble and B. Shepherd, Domination parameters for the bishops graph, Discrete Math., to appear. · Zbl 0602.05040
[5] Cockayne, E. J.; Hedetniemi, S. T., A note on the diagonal queens domination problem, J. Combin. Theory Ser. A, 41 (1986) · Zbl 0589.05014
[6] E.J. Cockayne and P.H. Spencer, An upper bound for the independent domination number of the queens graph, submitted.; E.J. Cockayne and P.H. Spencer, An upper bound for the independent domination number of the queens graph, submitted.
[7] De Jaenisch, C. F., Applications de l’Analyse Mathematique an Jeu des Echecs (1862), Petrograd
[8] Guy, R. K., Unsolved Problems in Number Theory, Vol. 1 (1981), Springer: Springer Berlin · Zbl 0474.10001
[9] Moser, L., On non-averaging sets of integers, Canad. J. Math., 5 (1953) · Zbl 0050.04001
[10] Riddell, J., On sets of numbers containing no \(l\) terms in arithmetic progression, Nieuw Arch. Wisk., XVII, 3, 204-209 (1969) · Zbl 0186.36101
[11] Roth, K. F., Sur quelques ensembles d’entiers, C.R. Acad. Sci. Paris, 234, 388-390 (1952) · Zbl 0046.04302
[12] Roth, K. F., On certain sets of integers, J. London Math. Soc., 28, 104-109 (1953) · Zbl 0050.04002
[13] Rouse Ball, W. W., Mathematical Recreations and Problems of Past and Present Times (1892), Macmillan: Macmillan London · JFM 24.0199.01
[14] P.H. Spencer, private communication.; P.H. Spencer, private communication.
[15] L. Welch, private communication.; L. Welch, private communication.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.