The -queen graphs have nice embeddings,
illustrated above. In general, the embedding with vertices corresponding to squares
of the chessboard has edges which overlap other edges
when drawn as straight lines, the only nontrivial exception being the -queen graph.
Up to interchange of
and , the only perfect
queen graphs are ,
, and .
A closed formula for the number of 4-cycles of is given by
where
is the floor function (Voropaev and Perepechko
2012).
Counting each Hamiltonian cycle separately from its reversal, the numbers for the -queen graphs for , 3, ... are 6, 3920, ... (OEIS A158663).
The corresponding numbers of Hamiltonian paths,
also counting reversals separately, are 24, 45856, ... (OEIS A158664).
Since each row and column of an -queen graph is an -clique, these graphs
have chromatic number at least . When , colors suffice. The chromatic
numbers for ,
3, ... are 4, 5, 5, 5, 7, 7, 9, 10, 11, 11, 12, 13, ... (OEIS A088202).
Assume .
Queen graphs
are class 1 when at least one of or
is even, and also when and
are both odd with . Jarnicki et al. (2017, pp. 433-435)
further proved that they are class 1 for . For odd and with , they are class
2 (Jarnicki et al. 2017, p. 433). These results leave a gap only
for odd and
satisfying .
Jarnicki et al. (2017, p. 435) computationally resolved all cases with
, supporting their conjecture
that a queen graph is class 2iff
it is an overfull graph.
Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc.
Math.163, 47-66, 1997.Chandra, A. K. "Independent
Permutations, as Related to a Problem of Moser and a Theorem of Pólya."
J. Combin. Th. Ser. A16, 111-120, 1974.Chvátal,
V. "Coloring the Queens Graph." https://users.encs.concordia.ca/~chvatal/queengraphs.html.Cockayne,
E. J. and Hedetniemi, S. T. "On the Diagonal Queens Domination Problem."
J. Combin. Th. Ser. A42, 137-139, 1986.Finozhenok, D.
and Weakley, W. D. "An Improved Lower Bound for Domination Numbers of the
Queen's Graph." Australasian J. Combin.37, 295-300, 2007.Fricke,
G. H.; Hedetniemi, S. M.; Hedetniemi, S. T.; McRae, A. A.; Wallis,
C. K.; Jacobson, M. S.; Martin, H. W.; and Weakley, W. D. "Combinatorial
Problems on Chessboards: A Brief Survey." In Proc. Seventh Quadrennial International
Conference on the Theory and Applications of Graphs: Graph Theory, Combinatorics,
and Algorithms, Vol. 1 (Ed. Y. Alavi and A. Schwenk). New York:
Wiley, pp. 507-528, 1995.Gardner, M. The
Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University
of Chicago Press, pp. 116-118 and 124-126, 1984.Gardner, M. The
Unexpected Hanging and Other Mathematical Diversions. Chicago, IL: Chicago
University Press, p. 191, 1991.Gosset, T. "The Eight Queens
Problem." Mess. Math.44, 48, 1914.House of Graphs.
Queen Graphs. Singleton Graph,
Tetrahedron K4, K6
- 2K2, Complement of 2P4,
K9 - C8, and others.Hwang,
F. K. and Lih, K. W. "Latin Squares and Superqueens." J. Combin.
Th. Ser. A34, 110-114, 1983.Jarnicki, W.; Myrvold, W.; Saltzman,
P.; and Wagon, S. "Properties, Proved and Conjectured, of Keller, Mycielski,
and Queen Graphs." Ars Math. Contemp.13, 427-460, 2017. https://doi.org/10.26493/1855-3974.1143.844.Karavaev,
A. M. "FlowProblem: Statistics of Simple Cycles." https://web.archive.org/web/20161015201528/http://flowproblem.ru/cycles/statistics-of-simple-cycles.Östergård,
P. R. J. and Weakley, W. D. "Values of Domination Numbers of
the Queen's Graph." Elec. J. Combin.8, No. 1, R29, 2001.
https://doi.org/10.37236/1573.Shapiro,
H. D. "Generalized Latin Squares on the Torus," Disc. Math.24,
63-77, 1978.Sloane, N. J. A. Sequences A088202,
A158663, and A158664
in "The On-Line Encyclopedia of Integer Sequences."Vasquez,
M. "New Results on the Queens Graph Coloring Problems." J. Heuristics10,
407-413, 2004.Voropaev, A. N. and Perepechko, S. N. "The
Number of Fixed Length Cycles in Undirected Graph: Explicit Formula in Case of Small
Lengths." Discrete Contin. Models Appl. Comput. Sci. No. 2, 6-12,
2012. https://journals.rudn.ru/miph/article/view/8653.Wagon,
S. "Graph Theory Problems from Hexagonal and Traditional Chess." College
Math. J.45, 278-287, 2014.
queen graph 
is a graph with 
vertices in which each vertex represents a square in an 
chessboard, and each
edge corresponds to a legal move by a queen, where
and 
are positive integers.
-queen graphs have nice embeddings,
illustrated above. In general, the embedding with vertices corresponding to squares
of the chessboard has edges which overlap other edges
when drawn as straight lines, the only nontrivial exception being the 
-queen graph.
"Queen", 
m, n
].
minus a cycle graph 
-queen graph
-knight graph
-queen
graph
-queen
graph
-knight graph
are Hamiltonian and biconnected.
The singleton graph 
is Hamiltonian by convention, while 
and 
are not. Up to interchange of 
and 
,
the planar queen graphs are 
for 
and 
, while the regular
queen graphs are 
and 
. The latter is isomorphic
to the tetrahedral graph 
.
and 
, the only perfect
queen graphs are 
,
, and 
.
of 4-cycles of 
is given by
is the floor function (Voropaev and Perepechko
2012).
-queen graphs for 
, 3, ... are 6, 3920, ... (OEIS A158663).
The corresponding numbers of Hamiltonian paths,
also counting reversals separately, are 24, 45856, ... (OEIS A158664).
-queen graph is an 
-clique, these graphs
have chromatic number at least 
. When 
, 
colors suffice. The chromatic
numbers for 
,
3, ... are 4, 5, 5, 5, 7, 7, 9, 10, 11, 11, 12, 13, ... (OEIS A088202).
.
Queen graphs 
are class 1 when at least one of 
or 
is even, and also when 
and 
are both odd with 
. Jarnicki et al. (2017, pp. 433-435)
further proved that they are class 1 for 
. For odd 
and 
with 
, they are class
2 (Jarnicki et al. 2017, p. 433). These results leave a gap only
for odd 
and 
satisfying 
.
Jarnicki et al. (2017, p. 435) computationally resolved all cases with
, supporting their conjecture
that a queen graph is class 2 iff
it is an overfull graph.
Graph Coloring Problems." J. Heuristics 10,
407-413, 2004.Voropaev, A. N. and Perepechko, S. N. "The
Number of Fixed Length Cycles in Undirected Graph: Explicit Formula in Case of Small
Lengths." Discrete Contin. Models Appl. Comput. Sci. No. 2, 6-12,
2012.