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.
The connected components of an 👁 (m,n)
-bishop graph corresponding to bishops moving on white
squares and black squares (i.e., the white bishop
graph and black bishop graph, respectively),
illustrated above for small square chessbaords, are isomorphic iff 👁 m
and 👁 n
are not both odd. Note that here, "white" and "black"
refer to the color of the squares a given bishop moves on irrespective of the color
of the bishop piece itself.
Closed formulas for the numbers 👁 c_k
of 👁 k
-graph cycles of 👁 B(n,n)
are given by
and
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, Queen Graph, Rook Graph, Triangular Honeycomb Bishop Graph, White Bishop GraphExplore with Wolfram|Alpha
More things to try:
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."Wagon, S. "Graph Theory Problems from Hexagonal and Traditional Chess." College Math. J. 45, 278-287, 2014.Referenced on Wolfram|Alpha
Bishop GraphCite this as:
Weisstein, Eric W. "Bishop Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BishopGraph.html