Lesson plan

King's graph

In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m king's graph is a king's graph of an n \times m chessboard. It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs. For an n \times m king's graph the total number of vertices is n m and the number of edges is 4nm -3(n + m) + 2 . For a square n \times n king's graph this simplifies so that the total number of vertices is n^2 and the total number of edges is (2n-2)(2n-1) . The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata. A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph.…

Back to article

Article summary

In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m king's graph is a king's graph of an n \times m chessboard. It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs. For an n \times m king's graph the total number of vertices is n m and the number of edges is 4nm -3(n + m) + 2 . For a square n \times n king's graph this simplifies so that the total number of vertices is n^2 and the total number of edges is (2n-2)(2n-1) . The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata. A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.