國王圖

國王圖是一個具有 個頂點的圖，其中每個頂點代表一個 棋盤上的一個方格，每條邊對應於國王的合法移動。它對應於兩個 路徑圖的 強圖積 。

從棋盤抽象出來的 國王圖如上圖所示，適用於 , ..., 6。 國王圖是 單例圖 ，而 國王圖同構於 四面體圖 。

國王圖中的邊數為 ，因此對於 , 2, ..., 前幾個值是 0, 6, 20, 42, 72, 110, ... (OEIS A002943)。

階數為 的圖的色數對於 為 ，對於 為 。對於 , 3, ..., 邊色數為 3, 8, 8, 8, 8, ....

國王圖在 Wolfram 語言中實現為GraphData["King", m, n].

所有的國王圖都是 哈密頓圖 且 雙連通的。唯一的 正則 國王圖是 -國王圖，它與 四面體圖 同構。 -國王圖僅當 時是 平面圖 (其中 的情況對應於 路徑圖) 和 ，其中一些嵌入方式如上所示。

-國王圖是 完美圖 的充要條件 是 (S. Wagon, 私人通訊, 2 月 22 日, 2013 年)。

對於 中 的 -環的數量 的閉合公式由下式給出

			(1)
			(2)
			(3)
			(4)

其中 的公式出現在 Perepechko 和 Voropaev 的著作中。

對於 -國王圖，, 3, ... 的 哈密頓環 的數量為 6, 32, 5660, 4924128, ... (OEIS A140521)，相應的 哈密頓路徑 的數量由 24, 784, 343184, ... (OEIS A158651) 給出。

Mertens (2024) 計算了 國王圖直至 的 支配多項式 和 支配集 的數量。