In mathematics, a bishop's graph is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
that represents all legal moves of the
chess piece the
bishop
A bishop is an ordained clergy member who is entrusted with a position of authority and oversight in a religious institution.
In Christianity, bishops are normally responsible for the governance of dioceses. The role or office of bishop is c ...
on a
chessboard. Each
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
* Vertex (computer graphics), a data structure that describes the positio ...
represents a square on the chessboard and each
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed ...
represents a legal move of the bishop; that is, there is an edge between two vertices (squares) if they occupy a common diagonal. When the chessboard has dimensions
, then the induced graph is called the
bishop's graph.
Properties
The fact that the chessboard has squares of two colors, say red and black, such that squares that are horizontally or vertically adjacent have opposite colors, implies that the bishop's graph has two connected components, whose vertex sets are the red and the black squares, respectively. The reason is that the bishop's diagonal moves do not allow it to change colors, but by one or more moves a bishop can get from any square to any other of the same color. The two components are isomorphic if the board has a side of even length, but not if both sides are odd.
A component of the bishop's graph can be treated as a
rook's graph
In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on ...
on a diamond if the original board is square and has sides of odd length, because if the red squares (say) are turned 45 degrees, the bishop's moves become horizontal and vertical, just like those of the
rook
Rook (''Corvus frugilegus'') is a bird of the corvid family. Rook or rooks may also refer to:
Games
*Rook (chess), a piece in chess
*Rook (card game), a trick-taking card game
Military
* Sukhoi Su-25 or Rook, a close air support aircraft
* USS ...
.
Domination
A square is said to be attacked by a bishop if the bishop can get to that square in exactly one move. A
dominating set
In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for .
The dominating set ...
is an arrangement of bishops such that every square is attacked or occupied by one of those bishops. An independent dominating set is a dominating set in which no bishop attacks any other. The minimum number of bishops needed to dominate a square board of side ''n'' is exactly ''n'', and this is also the smallest number of bishops that can form an independent dominating set.
By contrast, a total domination set, which is a dominating set for which every square, including those occupied by bishops, is attacked by one of the bishops, requires more bishops; on the square board of side ''n'' ≥ 3, the least size of a total dominating set is
about 1/3 larger than a minimum dominating set.
[E. J. Cockayne, B. Gamble, B. Shepherd, Domination parameters for the bishops graph, ''Discrete Mathematics'' 58 (1986), pp. 221–227.][E. J. Cockayne, Chessboard domination problems, ''Discrete Mathematics'' 86 (1990), pp. 13–20.]
References
{{reflist
Graph theory
Mathematical chess problems
Chess-related lists