Paper Info
Title
Values of Domination Numbers of the Queen's Graph
Abstract
The queen's graph Qn has the squares of the n n chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal. Let (Qn )a ndi(Qn) be the minimum sizes of a dominating set and an independent dominating set of Qn, respectively. Recent results, the Parallelogram Law, and a search algorithm adapted from Knuth are used to nd dominating sets. New values and bounds: (A) (Qn )= dn=2e is shown for 17 values of n (in particular, the set of values for which the conjecture (Q4k+1 )=2 k + 1 is known to hold is extended tok 32); (B) i(Qn )= dn=2e is shown for 11 values of n, including 5 of those from (A); (C) One or both of (Qn )a ndi(Qn) is shown to lie in fdn=2e, dn=2e +1 g for 85 values of n distinct from those in (A) and (B). Combined with previously published work, these results imply that for n 120, each of (Qn )a ndi(Qn) is either known, or known to have one of two values. Also, the general bounds (Qn) 69n=133 + O(1) and i(Qn) 61n=111 + O(1) are established.
Year
Venue
Keywords
2001
Electr. J. Comb.
dominating set,queen domination,queen's graph. supported by the academy of finland.,search algorithm,domination number
Field
DocType
Volume
Diagonal,Discrete mathematics,Graph,Dominating set,Combinatorics,Search algorithm,Vertex (geometry),Parallelogram law,Conjecture,Mathematics
Journal
8
Issue
Citations 
PageRank 
1
8
0.77
References 
Authors
5
2
Name
Order
Citations
PageRank
Patric R. J. Östergård160970.61
William D. Weakley25610.40