# Chessboard graphs¶

The methods defined here appear in sage.graphs.graph_generators.

• BishopGraph

• KingGraph

• KnightGraph

• QueenGraph

• RookGraph

AUTHORS:

• David Coudert (2012)

Return the $$d$$-dimensional Bishop Graph with prescribed dimensions.

The 2-dimensional Bishop Graph of parameters $$n$$ and $$m$$ is a graph with $$nm$$ vertices in which each vertex represents a square in an $$n \times m$$ chessboard, and each edge corresponds to a legal move by a bishop.

The $$d$$-dimensional Bishop Graph with $$d >= 2$$ has for vertex set the cells of a $$d$$-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a bishop in any pairs of dimensions.

The Bishop Graph is not connected.

INPUT:

• dim_list – iterable (list, set, dict); provides the dimensions $$n_1, n_2, \ldots, n_d$$, with $$n_i \geq 1$$, of the chessboard

• radius – integer (default: None); by setting the radius to a positive integer, one may decrease the power of the bishop to at most radius steps.

• relabel – boolean (default: False); indicates whether the vertices must be relabeled as integers

EXAMPLES:

The (n,m)-Bishop Graph is not connected:

sage: G = graphs.BishopGraph( [3, 4] )
sage: G.is_connected()
False


The Bishop Graph can be obtained from Knight Graphs:

sage: for d in range(3,12):   # long time
....:     H = Graph()
....:     for r in range(1,d+1):
....:         if not B.is_isomorphic(H):
....:            print("that's not good!")


Return a Graph built on a $$d$$-dimensional chessboard with prescribed dimensions and interconnections.

This function allows to generate many kinds of graphs corresponding to legal movements on a $$d$$-dimensional chessboard: Queen Graph, King Graph, Knight Graphs, Bishop Graph, and many generalizations. It also allows to avoid redundant code.

INPUT:

• dim_list – iterable (list, set, dict); provides the dimensions $$n_1, n_2, \ldots, n_d$$, with $$n_i \geq 1$$, of the chessboard

• rook – boolean (default: True); indicates whether the chess piece is able to move as a rook, that is at any distance along a dimension

• rook_radius – integer (default: None); restriction on the rook-like movements to distance at most rook_radius

• bishop – boolean (default: True); indicates whether the chess piece is able to move like a bishop, that is along diagonals

• bishop_radius – integer (default: None); restriction on the bishop-like movements to distance at most bishop_radius

• knight – boolean (default: True); indicating whether the chess piece is able to move like a knight

• knight_x – integer (default: 1); indicates the number on steps the chess piece moves in one dimension when moving like a knight

• knight_y – integer (default: 2); indicates the number on steps the chess piece moves in the second dimension when moving like a knight

• relabel – boolean (default: False); indicates whether the vertices must be relabeled as integers

OUTPUT:

• A Graph build on a $$d$$-dimensional chessboard with prescribed dimensions, and with edges according given parameters.

• A string encoding the dimensions. This is mainly useful for providing names to graphs.

EXAMPLES:

A $$(2,2)$$-King Graph is isomorphic to the complete graph on 4 vertices:

sage: G, _ = graphs.ChessboardGraphGenerator( [2,2] )
sage: G.is_isomorphic( graphs.CompleteGraph(4) )
True


A Rook’s Graph in 2 dimensions is isomorphic to the Cartesian product of 2 complete graphs:

sage: G, _ = graphs.ChessboardGraphGenerator([3,4], rook=True, rook_radius=None, bishop=False, knight=False)
sage: H = (graphs.CompleteGraph(3)).cartesian_product(graphs.CompleteGraph(4))
sage: G.is_isomorphic(H)
True


Return the $$d$$-dimensional King Graph with prescribed dimensions.

The 2-dimensional King Graph of parameters $$n$$ and $$m$$ is a graph with $$nm$$ vertices in which each vertex represents a square in an $$n \times m$$ chessboard, and each edge corresponds to a legal move by a king.

The d-dimensional King Graph with $$d >= 2$$ has for vertex set the cells of a d-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a king in either one or two dimensions.

All 2-dimensional King Graphs are Hamiltonian, biconnected, and have chromatic number 4 as soon as both dimensions are larger or equal to 2.

INPUT:

• dim_list – iterable (list, set, dict); provides the dimensions $$n_1, n_2, \ldots, n_d$$, with $$n_i \geq 1$$, of the chessboard

• radius – integer (default: None); by setting the radius to a positive integer, one may increase the power of the king to at least radius steps. When the radius equals the higher size of the dimensions, the resulting graph is a Queen Graph.

• relabel – boolean (default: False); indicates whether the vertices must be relabeled as integers

EXAMPLES:

The $$(2,2)$$-King Graph is isomorphic to the complete graph on 4 vertices:

sage: G = graphs.QueenGraph( [2, 2] )
sage: G.is_isomorphic( graphs.CompleteGraph(4) )
True


The King Graph with large enough radius is isomorphic to a Queen Graph:

sage: G = graphs.KingGraph( [5, 4], radius=5 )
sage: H = graphs.QueenGraph( [4, 5] )
sage: G.is_isomorphic( H )
True


Also True in higher dimensions:

sage: G = graphs.KingGraph( [2, 5, 4], radius=5 )
sage: H = graphs.QueenGraph( [4, 5, 2] )
sage: G.is_isomorphic( H )
True

sage.graphs.generators.chessboard.KnightGraph(dim_list, one=1, two=2, relabel=False)

Return the d-dimensional Knight Graph with prescribed dimensions.

The 2-dimensional Knight Graph of parameters $$n$$ and $$m$$ is a graph with $$nm$$ vertices in which each vertex represents a square in an $$n \times m$$ chessboard, and each edge corresponds to a legal move by a knight.

The d-dimensional Knight Graph with $$d >= 2$$ has for vertex set the cells of a d-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a knight in any pairs of dimensions.

The $$(n,n)$$-Knight Graph is Hamiltonian for even $$n > 4$$.

INPUT:

• dim_list – iterable (list, set, dict); provides the dimensions $$n_1, n_2, \ldots, n_d$$, with $$n_i \geq 1$$, of the chessboard

• one – integer (default: 1); indicates the number of steps in the first dimension

• two – integer (default: 2); indicates the number of steps in the second dimension

• relabel – boolean (default: False); indicates whether the vertices must be relabeled as integers

EXAMPLES:

The $$(3,3)$$-Knight Graph has an isolated vertex:

sage: G = graphs.KnightGraph( [3, 3] )
sage: G.degree( (1,1) )
0


The $$(3,3)$$-Knight Graph minus vertex (1,1) is a cycle of order 8:

sage: G = graphs.KnightGraph( [3, 3] )
sage: G.delete_vertex( (1,1) )
sage: G.is_isomorphic( graphs.CycleGraph(8) )
True


The $$(6,6)$$-Knight Graph is Hamiltonian:

sage: G = graphs.KnightGraph( [6, 6] )
sage: G.is_hamiltonian()
True


Return the $$d$$-dimensional Queen Graph with prescribed dimensions.

The 2-dimensional Queen Graph of parameters $$n$$ and $$m$$ is a graph with $$nm$$ vertices in which each vertex represents a square in an $$n \times m$$ chessboard, and each edge corresponds to a legal move by a queen.

The $$d$$-dimensional Queen Graph with $$d >= 2$$ has for vertex set the cells of a $$d$$-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a queen in either one or two dimensions.

All 2-dimensional Queen Graphs are Hamiltonian and biconnected. The chromatic number of a $$(n,n)$$-Queen Graph is at least $$n$$, and it is exactly $$n$$ when $$n\equiv 1,5 \bmod{6}$$.

INPUT:

• dim_list – iterable (list, set, dict); provides the dimensions $$n_1, n_2, \ldots, n_d$$, with $$n_i \geq 1$$, of the chessboard

• radius – integer (default: None); by setting the radius to a positive integer, one may reduce the visibility of the queen to at most radius steps. When radius is 1, the resulting graph is a King Graph.

• relabel – boolean (default: False); indicates whether the vertices must be relabeled as integers

EXAMPLES:

The $$(2,2)$$-Queen Graph is isomorphic to the complete graph on 4 vertices:

sage: G = graphs.QueenGraph([2, 2])
sage: G.is_isomorphic(graphs.CompleteGraph(4))
True


The Queen Graph with radius 1 is isomorphic to the King Graph:

sage: G = graphs.QueenGraph([4, 5], radius=1)
sage: H = graphs.KingGraph([5, 4])
sage: G.is_isomorphic(H)
True


Also True in higher dimensions:

sage: G = graphs.QueenGraph([3, 4, 5], radius=1)
sage: H = graphs.KingGraph([5, 3, 4])
sage: G.is_isomorphic(H)
True


The Queen Graph can be obtained from the Rook Graph and the Bishop Graph:

sage: for d in range(3,12):   # long time
....:     for r in range(1,d+1):
....:         if not G.is_isomorphic(H):
....:             print("that's not good!")


Return the $$d$$-dimensional Rook’s Graph with prescribed dimensions.

The 2-dimensional Rook’s Graph of parameters $$n$$ and $$m$$ is a graph with $$nm$$ vertices in which each vertex represents a square in an $$n \times m$$ chessboard, and each edge corresponds to a legal move by a rook.

The $$d$$-dimensional Rook Graph with $$d >= 2$$ has for vertex set the cells of a $$d$$-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a rook in any of the dimensions.

The Rook’s Graph for an $$n\times m$$ chessboard may also be defined as the Cartesian product of two complete graphs $$K_n \square K_m$$.

INPUT:

• dim_list – iterable (list, set, dict); provides the dimensions $$n_1, n_2, \ldots, n_d$$, with $$n_i \geq 1$$, of the chessboard

• radius – integer (default: None); by setting the radius to a positive integer, one may decrease the power of the rook to at most radius steps. When the radius is 1, the resulting graph is a $$d$$-dimensional grid.

• relabel – boolean (default: False); indicates whether the vertices must be relabeled as integers

EXAMPLES:

The $$(n,m)$$-Rook’s Graph is isomorphic to the Cartesian product of two complete graphs:

sage: G = graphs.RookGraph( [3, 4] )
sage: H = ( graphs.CompleteGraph(3) ).cartesian_product( graphs.CompleteGraph(4) )
sage: G.is_isomorphic( H )
True


When the radius is 1, the Rook’s Graph is a grid:

sage: G = graphs.RookGraph( [3, 3, 4], radius=1 )
sage: H = graphs.GridGraph( [3, 4, 3] )
sage: G.is_isomorphic( H )
True