Queen Graph

The  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. The -queen graphs have nice embeddings, illustrated above. In general, the default embedding with vertices corresponding to squares of the chessboard has degenerate superposed edges, the only nontrivial exception being the -queen graph.

Queen graphs are implemented in the Wolfram Language as GraphData["Queen", m, n].

The following table summarized some special cases of queen graphs.

	name
	complete graph
	tetrahedral graph

The following table summarizes some named graph complements of queen graphs.

-queen graph	-knight graph
-queen graph
-queen graph	-knight graph

All queen graphs are Hamiltonian and biconnected. The only planar and only regular queen graph is the -queen graph, which is isomorphic to the tetrahedral graph .

The only perfect queen graphs are , , and .

A closed formula for the number of 4-cycles of  is given by

(Perepechko and Voropaev).

The numbers of Hamiltonian cycles for the -queen graphs for , 3, ... are 6, 3920, ... (OEIS A158663), with the corresponding numbers of Hamiltonian paths given by 24, 45856, ... (OEIS A158664).

Since each row and column of an -queen graph is an -clique, these graphs have chromatic number at least . And in fact, when , it can be shown that  colors suffice. In fact, 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 (J. DeVincentis and S. Wagon, pers. comm., Nov. 13-14, 2011) and when  and  are both odd with  (S. Wagon, pers. comm., Dec. 9, 2015). On the other hand, a queen graph with  odd and  is trivially class 2 (S. Wagon, pers. comm., Dec. 9, 2015), which leaves only the case of odd  with  open.

REFERENCES

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. A 16, 111-120, 1974.

Chvátal, V. "Coloring the Queens Graph." http://users.encs.concordia.ca/~chvatal/queengraphs.html.

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.; Hedemiemi, S. M.; Hedetniemi, S. T.; McRae. A. A.; Wallis, C. K.; Jacobsen, M. S.; Martinand, H. W.; abd Weakley, W. D. "Combinatorial Problems on Chessboards: A Brief Survey." In Graph Theory, Combinatoricsand Applications, Vol. I, Prec. Seventh QuadrennialConf.on the Theory and Application sof Graphs (Ed. Alavi and Schwenk). Western Michigan University, 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. Mess. Math. 44, 48, 1914.

Hwang, F. K. and Lih, K. W. "Latin Squares and Superqueens." J. Combin. Th. Ser. A 34, 110-114, 1983.

Jarnicki, W.; Myrvold, W.; Saltzman, P.; and Wagon, S. "Properties, Proved and Conjectured, of Keller, Mycielski, and Queen Graphs." To appear in Ars Math. Comtemp. 2017.Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/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, Issue 1, No. R29, 2001.

 https://www.combinatorics.org/ojs/index.php/eljc/article/view/v8i1r29.Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Sloane, N. J. A. Sequence A088202, A158663, and A158664 in "The On-Line Encyclopedia of Integer Sequences."Shapiro, H. D. "Generalized Latin Squares on the Torus," Disc. Math. 24, 63-77, 1978.

Vasquez, M. "New Results on the Queens  Graph Coloring Problems." J. Heuristics 10, 407-413, 2004.Wagon, S. "Graph Theory Problems from Hexagonal and Traditional Chess." College Math. J. 45, 278-287, 2014.