TOPICS
Search

Bishop Graph


A bishop graph is a graph formed from possible moves of a bishop chess piece, which may make diagonal moves of any length on a chessboard (or any other board). To form the graph, each chessboard square is considered a vertex, and vertices connected by allowable bishop moves are considered edges.

Because bishops starting on squares of one color and moving diagonally always remain on the same color squares, all bishop graphs are disconnected (except for the trivial singleton graph on a 1×1 board which is trivially connected).

Special cases are summarized in the following table.

(m,n)-bishop graphgraph
(1,n)n-empty graph K^__n
(2,n)2 n-path graphs 2P_n

The black/white components of an (m,n)-bishop graph (i.e., white bishop graph and black bishop graph) are isomorphic iff m and n are not both odd.

Closed formulas for the numbers c_k of k-graph cycles of B(n,n) are given by

c_3=1/6(n-2)(n-1)^2n
(1)
c_4=1/(30)(n-2)(n-1)n(3n^2-11n+11)
(2)

and

 840c_6=n(n-1)(40n^5-289n^4+887n^3-2193n^2+3792n-1934)-210(n^2-12n+26)|_1/2n_|
(3)

for n!=3, 7, ..., the last of which is due to Perepechko and Voropaev.

S. Wagon (pers. comm., Aug. 17, 2012) showed that the (m,n)-white bishop graph B(m,n) is Hamiltonian for 4<=m<=n and when m=3 and n>=4, and nonhamiltonian for (m,n)=(3,3) and the trivial cases m=2 or 1.

All bishop graphs are perfect.


See also

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

Explore with Wolfram|Alpha

References

Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."

Cite this as:

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

Subject classifications