Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Values of Domination Numbers of the Queen’s Graph. | Values of Domination Numbers of the Queen s Graph Patric R. J. Ostergảrd Department of Computer Science and Engineering Helsinki University of Technology . Box 5400 02015 HUT Finland William D. Weakley Department of Mathematical Sciences Indiana University - Purdue University Fort Wayne Fort Wayne Indiana 46805 weakley@ Submitted November 7 2000 Accepted March 26 2001. MR Subject Classifications 05C69 68R05 Abstract The queen s graph Qn has the squares of the n X n chessboard as its vertices two squares are adjacent if they are in the same row column or diagonal. Let c Qn and i 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 find dominating sets. New values and bounds A Y Qn n 2 is shown for 17 values of n in particular the set of values for which the conjecture Y Q4k 1 2k 1 is known to hold is extended to k 32 B i Qn n 2 is shown for 11 values of n including 5 of those from A C One or both of Y Qn and i Qn is shown to lie in n 2 n 2 1 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 Y Qn and i Qn is either known or known to have one of two values. Also the general bounds y Qn 69n 133 0 1 and i Qn 61n 111 0 1 are established. Keywords dominating set queen domination queen s graph. Supported by the Academy of Finland. THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R29 1 1 Introduction The queen s graph Qn has the squares of the n X n chessboard as its vertices two squares are adjacent if they are in the same row column or diagonal. A set D of squares of Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a square in D. If no two squares of a set I are adjacent then I is an independent set. Let Y Qn denote the minimum size of a dominating set for Qn a dominating set of this size .
