国王图

国王图是一个具有 个顶点的图，其中每个顶点代表一个 棋盘上的一个方格，每条边对应于国王的合法移动。它对应于两个 路径图的 强图积 。

从棋盘抽象出来的 国王图如上图所示，适用于 , ..., 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) 计算了 国王图直至 的 支配多项式 和 支配集 的数量。