Upper bounds for the domination numbers of toroidal queens graphs

• Autorzy: Christina M. Mynhardt
• Języki publikacji: EN

Abstrakty

EN

We determine upper bounds for $γ(Qn^t)$ and $i(Qₙ^t)$, the domination and independent domination numbers, respectively, of the graph $Qₙ^t$ obtained from the moves of queens on the n×n chessboard drawn on the torus.

Słowa kluczowe

EN

queens graph; toroidal chessboards; queens domination problem

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2003
• Tom: 23
• Numer: 1
• Strony: 163-175

Daty

wydano

2003

otrzymano

2001-10-02

poprawiono

2002-01-18

Twórcy

autor

Christina M. Mynhardt

• Department of Mathematics, University of South Africa, P.O. Box 392 Unisa 0003 South Africa

Bibliografia

• [1] W. Ahrens, Mathematische Unterhalten und Spiele (B.G. Teubner, Leipzig-Berlin, 1910).
• [2] M. Bezzel, Schachfreund, Berliner Schachzeitung, 3 (1848) 363.
• [3] A.P. Burger, E.J. Cockayne and C.M. Mynhardt, Queens graphs for chessboards on the torus, Australas. J. Combin. 24 (2001) 231-246.
• [4] A.P. Burger and C.M. Mynhardt, Symmetry and domination in queens graphs, Bulletin of the ICA 29 (2000) 11-24.
• [5] A.P. Burger and C.M. Mynhardt, Properties of dominating sets of the queens graph $Q{4k+3}$, Utilitas Math. 57 (2000) 237-253.
• [6] A.P. Burger and C.M. Mynhardt, An improved upper bound for queens domination numbers, Discrete Math., to appear.
• [7] A.P. Burger, C.M. Mynhardt and W.D. Weakley, The domination number of the toroidal queens graph of size 3k × 3k, Australas. J. Combin., to appear.
• [8] E.J. Cockayne, Chessboard Domination Problems, Discrete Math. 86 (1990) 13-20, doi: 10.2307/2325220.
• [13] P.R.J. Östergå rd and W.D. Weakley, Values of domination numbers of the queen's graph, Electron. J. Combin. 8 (2001) no. 1, Research paper 29, 19 pp.
• [14] W.D. Weakley, Domination In The Queen's Graph, in: Y. Alavi and A.J. Schwenk, eds, Graph Theory, Combinatorics, and Algorithms, Volume 2, pages 1223-1232 (Wiley-Interscience, New York, 1995).
• [15] W.D. Weakley, A lower bound for domination numbers of the queen's graph, J. Combin. Math. Combin. Comput., to appear.
• [16] W.D. Weakley, Upper bounds for domination numbers of the queen's graph, Discrete Math. 242 (2002) 229-243, doi:10.1016/S0012-365X(00)00467-2.

Identyfikatory

DOI

10.7151/dmgt.1193