TOPICS
Search

Queen Graph


QueensGraph

The m×n queen graph Q_(m,n) is a graph with mn vertices in which each vertex represents a square in an m×n chessboard, and each edge corresponds to a legal move by a queen. The (2,n)-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 (2,2)-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.

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

GG^_
(2,3)-queen graph(2,3)-knight graph
(2,4)-queen graph2P_4
(3,3)-queen graph(3,3)-knight graph

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

The only perfect queen graphs are Q_(1,n), Q_(2,n), and Q_(3,3).

A closed formula for the number of 4-cycles of Q(n,n) is given by

 60c_4=n(n-1)(21n^3+526n^2-1709n+996)-60(3n^2-12n+4)|_1/2n_|

(Perepechko and Voropaev).

The numbers of Hamiltonian cycles for the (n,n)-queen graphs for n=2, 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 (n,n)-queen graph is an n-clique, these graphs have chromatic number at least n. And in fact, when n=1,5 (mod 6), it can be shown that n colors suffice. In fact, the chromatic numbers for n=2, 3, ... are 4, 5, 5, 5, 7, 7, 9, 10, 11, 11, 12, 13, ... (OEIS A088202).

Queen graphs Q_(m,n) are class 1 when at least one of m or n is even (J. DeVincentis and S. Wagon, pers. comm., Nov. 13-14, 2011) and when m and n are both odd with m<=n<=2m-1 (S. Wagon, pers. comm., Dec. 9, 2015). On the other hand, a queen graph with m,n odd and n>=(2m^3-11m+18)/3 is trivially class 2 (S. Wagon, pers. comm., Dec. 9, 2015), which leaves only the case of odd m,n with 2m-1<n<(2m^3-11m+18)/3 open.


See also

Bishop Graph, Black Bishop Graph, King Graph, Knight Graph, Queens Problem, Rook Graph, White Bishop Graph

Explore with Wolfram|Alpha

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 n^2 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.

Cite this as:

Weisstein, Eric W. "Queen Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/QueenGraph.html

Subject classifications