|
|
A075458
|
|
Domination number for queens' graph Q(n).
|
|
11
|
|
|
1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, 11, 11, 12, 12, 13, 13
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Minimum number of queens needed to occupy or attack all squares of an n X n chessboard.
a(n) >= ceiling(n/2) for all n, except n = 3, 11. See paper by Finozhenok and Weakley below.
a(n) = p or p+1, where p = ceiling(n/2), proved for all n <= 132, except n = 3, 11. See paper by Ostergard and Weakley below. Note that this implies that a(n+4) > a(n). (End)
|
|
REFERENCES
|
W. W. R. Ball and H. S. M. Coxeter, "Math'l Rec. and Essays," 13th Ed. Dover, p. 173.
John Watkins, Across the Board: The Mathematics of Chessboard Problems (2004), pp. 113-137
|
|
LINKS
|
Irene Choi, Shreyas Ekanathan, Aidan Gao, Tanya Khovanova, Sylvia Zia Lee, Rajarshi Mandal, Vaibhav Rastogi, Daniel Sheffield, Michael Yang, Angela Zhao, and Corey Zhao, The Struggles of Chessland, arXiv:2212.01468 [math.HO], 2022.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1926, p. 49.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|