Abstract
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.
% is not representable in the same way.
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 grid or the hexagonal grid is a queens graph.
| Original language | English |
|---|---|
| Publication date | 2004 |
| Publication status | Published - 2004 |
| Event | Graph Theory 2004: a conference in memory of Claude Berge - Paris Duration: 1 Jan 2004 → … |
Conference
| Conference | Graph Theory 2004: a conference in memory of Claude Berge |
|---|---|
| City | Paris |
| Period | 01/01/2004 → … |