King's Graphs Lecture Notes

Introduction to King's Graphs

• An n-by-k king's graph is a graph representing legal moves of a king on an n-by-k chessboard.
• Each vertex represents a square on the chessboard.
• Each edge represents a legal move of a king, which can move one square in any direction.

Dimensions and Construction

• King's graphs can vary in dimensions, e.g., 3x5, 6x7, etc.
• Defined as the strong product of two path graphs:
  • A path graph with n vertices and a path graph with k vertices.
• Example: A 3x4 king's graph = strong product of a three-vertex path graph and a four-vertex path graph.

Strong Product and Chessboard Analogy

• 8x8 king's graph: Strong product of two path graphs with eight vertices each.
• Chessboard labeling:
  • Rows: Numbers 1 through 8
  • Columns: Letters a through h
• Example move: King at b1 can move to a1, c1, b2, a2, and c2.

Characteristics of King's Graphs

Adjacency Rules

1. Same column & consecutive rows: Vertices with the same column letter and consecutive row numbers connect.
2. Same row & consecutive columns: Vertices with the same row number and consecutive column letters connect.
3. Diagonal connection: Vertices with consecutive row numbers and column letters connect.

Strong Product Rules

• First adjacency rule: Connect vertices with same letters and consecutive numbers.
• Second adjacency rule: Connect vertices with same numbers and consecutive letters.
• Third adjacency rule: Connect vertices with consecutive letters and numbers.

Properties of King's Graphs

Longest Shortest Path

• Longest shortest path is the maximum of (n, k).
• Calculation: Max of horizontal (H) or vertical (V) distances between vertices.

Number of Edges

• For an n-by-k king's graph:
  • Diagonal edges: 2 * (n - 1) * (k - 1)
  • Horizontal and vertical edges: n * (k - 1) + k * (n - 1)
  • Total edges formula: 4nk - 3(n + k) + 2

Chromatic Number

• Chromatic number is 4 if the minimum of n and k is greater than one.
• Reason: Presence of a 4-clique (four mutually adjacent vertices).
• Coloring method: Alternate colors within rows and switch schemes every row.

Conclusion

• Upcoming topics: Sperner's lemma and more chess-related graphs.
• Encouragement to like, share, and subscribe.
• Closing remarks: Have a great day!