超立方体图

维超立方体图，也称为 维立方体图，通常表示为 或 ，其顶点是 个符号 , ..., ，其中 或 1，并且当且仅当符号恰好在一个坐标中不同时，两个顶点相邻 iff。

维超立方体的图由 图笛卡尔积 路径图 给出。超立方体图 同构于 哈斯图，用于 布尔代数 在 个元素上。 也同构于 单纯形图 的 完全图 （Alikhani 和 Ghanbari 2024）。

上面的图显示了一些小的 维超立方体图的垂直投影，使用了每个顶点集合的前两个 坐标。请注意，上面的 是沿着 空间对角线 查看的常用 立方体 的投影，使得顶部和底部顶点重合，因此只显示了立方体的八个顶点中的七个。此外，中心边的三个连接到上顶点，而另外三个连接到下顶点。

超立方体图可以使用 Wolfram 语言 中的命令计算HypercubeGraph[n]，超立方体图的预计算属性在 Wolfram 语言 中实现为GraphData["Hypercube"，n]。

下表总结了特殊情况。

0	单例图
1	路径图
2	正方形图
3	立方图
4	超立方体图

所有超立方体图都是 哈密顿图，标记的超立方体图的任何 哈密顿环 都定义了一个二进制反射 格雷码 (Skiena 1990, p. 149; Mütze 2024)。超立方体图也是 优美图 (Maheo 1980, Kotzig 1981, Gallian 2018)、对跖图 和（很可能）支配唯一图。

对于 、2、...， 维超立方体图上（有向）哈密顿路径的数量为 0, 0, 48, 48384, 129480729600, ... (OEIS A006070; 扩展了 Gardner 1986, pp. 23-24 的结果)，而（有向）哈密顿环的数量为 0, 2, 12, 2688, 1813091520, ... (Harary et al. 1988; OEIS A091299)。

长度为 的 环 的数量 在 中的闭合公式由 对于 奇数给出，并且

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

(E. Weisstein，2014 年 11 月 16 日和 2023 年 4 月 19 日)。

超立方体图是 距离传递 的，因此也是 距离正则 的。

1954 年，Ringel 表明，当 是 2 的幂时，超立方体图 允许 哈密顿分解 (Alspach 2010)。Alspach et al. (1990) 表明，每个 对于 都允许 哈密顿分解。

对于 ，超立方体图也是 单位距离 的 (Gerbracht 2008)，如上面前几个超立方体图所示。这可以通过归纳法为 正方形图 的单位距离嵌入开始，将嵌入在一个之前步骤中未选择的方向上平移一个单位（只使用了有限个单位平移向量，因此必须有一个之前未使用的方向），将平移中的顶点与原始顶点中的对应顶点连接起来，并重复直到 维超立方体图构造完成，从而为 维超立方体图建立。

确定 支配数 本质上是困难的 (Azarija et al. 2017)，截至 2018 年 4 月，仅已知高达 的值 (Östergård 和 Blass 2001, Bertolo et al. 2004)。Azarija et al. (2017) 表明，超立方体图的支配数和 全支配数 通过 相关联。

对于 ， 是平面的，因此对于 ，具有 图交叉数 。Eggleton 和 Guy (1970) 声称发现了 对于 的 图交叉数 的上限，其中

			(5)
			(6)

对于 、4、...，前几个值为 0、8、56、352、1760、8192、35712、... (OEIS A307813)。

后来发现了一个错误，但 Erdős 和 Guy (1973) 随后推测，不仅原始界限是正确的（尽管尚未证明），而且 (Clancy et al. 2019)。虽然已知 ，但对于更大的 的精确值尚不清楚 (Clancy et al. 2019)。但是，可以使用 QuickCross (Haythorpe) 直接计算上限，这对应于 Eggleton 和 Guy 对于 的值 (E. Weisstein，2019 年 4 月 30 日)。此外，Erdős 和 Guy (1973) 的猜想现在已被驳斥，因为已知 (Clancy et al. 2019)。