Misplaced Pages

Bishop's graph

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Mathematical graph relating to chess

In mathematics, a bishop's graph is a graph that represents all legal moves of the chess piece the bishop on a chessboard. Each vertex represents a square on the chessboard and each edge 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 m × n {\displaystyle m\times n} , then the induced graph is called the m × n {\displaystyle m\times n} 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 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.

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 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 2 ⌈ 2 ( n − 1 ) / 3 ⌉ , {\displaystyle 2\lceil 2(n-1)/3\rceil ,} about 1/3 larger than a minimum dominating set.

References

  1. Berghammer, Rudolf (2012). "Relation-algebraic modeling and solution of chessboard independence and domination problems". The Journal of Logic and Algebraic Programming. 81 (6): 625–642. doi:10.1016/J.JLAP.2012.05.001.
  2. Hedetniemi, Jason T.; Hedetniemi, Stephen T. (September 2020). "Domination in chessboards". In Haynes, Teresa W.; Hedetniemi, Stephen T.; Henning, Michael A. (eds.). Structures of Domination in Graphs. Developments in Mathematics. Vol. 66. Springer International Publishing. pp. 341–386. doi:10.1007/978-3-030-58892-2_12. ISBN 9783030588922.
  3. Cockayne, E. J.; Gamble, B.; Shepherd, B. (1986). "Domination parameters for the bishops graph". Discrete Mathematics. 58 (3): 221–227. doi:10.1016/0012-365X(86)90139-1.
  4. Cockayne, E. J. (1990). "Chessboard domination problems". Discrete Mathematics. 86 (1–3): 13–20. doi:10.1016/0012-365X(90)90344-H. hdl:1828/2415.
Categories: