κ-Dependence and Domination in Kings Graphs
Eugen J. Ionaşcu, Dan Pritikin, Stephen E. Wright · American Mathematical Monthly · 2008
For most choices of k = 0, ... , 8, there is a tidy solution: an upper bound can be proved by a short elementary argument, and an arrangement of kings can be con structed to show that the upper bound is tight. These limiting densities are given in Section 6. However, tight upper bounds are not yet known for either k = 4 or k ? 5. It is easy to construct arrangements of kings (on arbitrarily large boards) that achieve the densities of 3/5 and 9/13 for k ? 4 and 5, respectively. We conjecture that these are indeed the maximum limiting densities. The story in the present article concerns the struggle to support this conjecture by good upper bounds, as well as the variety of rival techniques used for different val ues of k. Along the way, we make elementary use of graph theory, number theory, group theory, real analysis, and integer linear programming. We believe the methods of the present paper can provide the basis for undergraduate research projects on re lated problems.