King Graph


The m×n king graph 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 king.

The number of edges in the n×n king graph is 2n(2n+1), so for n=1, 2, ..., the first few values are 0, 6, 20, 42, 72, 110, ... (OEIS A002943).

The order n graph has chromatic number gamma=1 for n=1 and gamma=4 for n>=2. For n=2, 3, ..., the edge chromatic numbers are 3, 8, 8, 8, 8, ....

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


All king graphs are Hamiltonian and biconnected. The only regular king graph is the (2,2)-king graph, which is isomorphic to the tetrahedral graph K_4. The (m,n)-king graphs are planar only for min(m,n)=1,2 (with the min(m,n)=1 case corresponding to path graphs) and (m,n)=(3,3), some embeddings of which are illustrated above.

The (m,n)-king graph is perfect iff min(m,n)<=3 (S. Wagon, pers. comm., Feb. 22, 2013).

Closed formulas for the numbers c_k of k-cycles of K(n,n) with n>=2 are given by


where the formula for c_5 appears in Perepechko and Voropaev.

The numbers of Hamiltonian cycles for the (n,n)-king graphs for n=2, 3, ... are 6, 32, 5660, 4924128, ... (OEIS A140521), with the corresponding numbers of Hamiltonian paths given by 24, 784, 343184, ... (OEIS A158651).

See also

Bishop Graph, Black Bishop Graph, Knight Graph, Rook Graph, White Bishop Graph

Explore with Wolfram|Alpha


Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles.", 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. Sequences A002943, A140521, and A158651 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "King Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications