1 Department of Mathematics, Technical University of Denmark2 unknown3 Department of Applied Mathematics and Computer Science, Technical University of Denmark
A graph G is a queens graph if the vertices of G can be mapped to queens on the chessboard such that two vertices are adjacent if and only if the corresponding queens attack each other, i.e. they are in horizontal, vertical or diagonal position. We prove a conjecture of Beineke, Broere and Henning that the Cartesian product of an odd cycle and a path is a queens graph. We show that the same does not hold for two odd cycles. The representation of the Cartesian product of an odd cycle and an even cycle remains an open problem. We also prove constructively that any finite subgraph of the rectangular grid or the hexagonal grid is a queens graph. Using a small computer search we solve another conjecture of the authors mentioned above, saying that K-3,K-4 minus an edge is a minimal non-queens graph.
Discrete Mathematics, 2006, Vol 306, Issue 12, p. 1105-1114