A contribution to queens graphs:: A substitution method

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. (c) 2006 Elsevier B.V. All rights reserved.