立方体连接环图

n 阶立方体连接环图是通过将 n 维超立方体中的每个顶点替换为长度为 n 的环而获得的图。它们由 Preparata 和 Vuillemin (1981) 引入，并与超立方体共享许多属性，但具有额外的理想属性，即对于 n>1，每个顶点都具有度数 3。立方体连接环对于 n=1 和 2 包含自环，但对于 n>=3 是简单图。

n 阶立方体连接环可以在由数字对 (x,y) 索引的 n·2^n 个节点的集合上构建，其中 0<=x<=2^n-1 且 0<=y<=n-1，其中每个节点 (x,y) 连接到另外三个节点 (x,(y+1) (mod n))、(x,(y-1) (mod n)) 和 (x 异或 2^y,y)，其中 A 异或 B 表示将 A 和 B 视为二进制数的按位异或运算。

n 阶立方体连接环也可以构建为作用于长度为 n 的二进制字的群的 Cayley 图，该群由将字的位向左旋转一个位置、将字的位向右旋转一个位置以及反转字的第一个位的群元素生成 (Akers and Krishnamurthy 1989; Annexstein et al. 1990)。

n=4 的情况是环面网格图 C_8 square C_8 的子图。

特殊情况 n=3 对应于截角立方体图，如上图所示的多种嵌入方式。

n 维立方体连接环图可以使用以下 Wolfram 语言生成：FromEntity[Entity["Graph", "CubeConnectedCycle", n]], 并且可以使用以下 Wolfram 语言获取小型立方体连接环图的预计算属性：GraphData["CubeConnectedCycle", n].

对于 n>3，立方体连接环图的图直径为 2n+|_n/2_|-2。

Sýkora 和 Vrt'o (1993) 建立了 n 维立方体连接环图的图交叉数的界限 (Clancy et al. 2019)。

(Clancy et al. 2019)。然而，与使用 QuickCross (Haythorpe) 可计算的上限相比，这些界限相当宽松，对于 n=3、4、5、... 和适度的运行时间，可以获得上限为 0、16、88、521、2623、... (E. Weisstein, 2019 年 4 月 29 日)。