zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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\sb n$ may be formed from an $n\times n$ chessboard and a chess piece $P$ by taking the $n\sp 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\sb n$ has the $n\sp 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.

05C99Graph theory
05C35Extremal problems (graph theory)
Full Text: DOI
[1] Behrend, F. A.: On sets of integers which contain no 3 terms in arithmetic progression. Proc. nat. Acad. sci. USA 32, 331-332 (1946) · Zbl 0060.10302
[2] Berge, C.: Theory of graphs and its applications. 40-51 (1962) · Zbl 0097.38903
[3] 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. · 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.
[7] De Jaenisch, C. F.: Applications de l’analyse mathematique an jeu des echecs. (1862)
[8] Guy, R. K.: Unsolved problems in number theory. 1 (1981) · 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. 17, No. 3, 204-209 (1969) · Zbl 0186.36101
[11] Roth, K. F.: Sur quelques ensembles d’entiers. CR 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] Ball, W. W. Rouse: Mathematical recreations and problems of past and present times. (1892) · Zbl 24.0199.01
[14] P.H. Spencer, private communication.
[15] L. Welch, private communication.