✦ LIBER ✦

On the queen domination problem

✍ Scribed by Charles M. Grinstead; Bruce Hahne; David Van Stone

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 393 KB
Volume: 86
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90345-i

No coin nor oath required. For personal study only.

✦ Synopsis

A configuration of queens on an m X m chessboard is said to dominate the board if every square either contains a queen or is attacked by a queen. The configuration is said to be non-attacking if no queen attacks another queen. Let f(m) and g(m) equal the minimum number of queens and the minimum number of non-attacking queens, respectively, needed to dominate an m x m chessboard. We prove that:

(1) f(m)sgm+O(l), and

(2) g(m) G $rn + O(1).

These are the best upper bounds known at the present time for these functions.

📜 SIMILAR VOLUMES

On the diagonal queens domination proble

On the diagonal queens domination problem

✍ E.J Cockayne; S.T Hedetniemi 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 135 KB

The weighted perfect domination problem

✍ Chain-Chin Yen; R.C.T. Lee 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 393 KB

On the modular n-queen problem

✍ Olof Heden 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 408 KB

Heden, O., On the modular n-queen problem, Discrete Mathematics 102 (1992) 155-161. Let M(n) denote the maximum number of queens on a modular chessboard such that no two attack each other. We prove that if 4 or 6 divides n then M(n) c n -2 and if gcd(n, 24) = 8 then M(n) 2 n -2. We also show that M

A new approach for the domination proble

A new approach for the domination problem on permutation graphs

✍ Y. Liang; C. Rhee; S.K. Dhall; S. Lakshmivarahan 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 933 KB

On a Nordhaus-Gaddum type problem for in

On a Nordhaus-Gaddum type problem for independent domination

✍ E.J. Cockayne; G. Fricke; C.M. Mynhardt 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 254 KB

Let i(G) (i(G), respectively) be the independent domination number (i.e. smallest cardinality of a maximal independent vertex subset) of the p-vertex graph G (the complement G of G, respectively). We prove limp~[max~ i(G)i(Cr)/p 2] = 1/16.

Domination and irredundance in the queen

Domination and irredundance in the queens' graph

✍ A.P Burger; E.J Cockayne; C.M Mynhardt 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 1020 KB

The vertices of the queem;' graph {~, are the squares of an n × n chessboard and two squares are adjacent ifa queen placed on one covers the other. It is shown that the domination num;~'r of Q. is at most 31n/54 + O(1), that Q. possesses minimal dominating sets of cardina~tty 5n/2 -O(l) and that the