主题
Search

折叠立方体图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
FoldedCubeGraph

折叠 n-立方体图，或许更应该称为“折叠超立方体图”，是通过合并 n-超立方体图 Q_n 中位于对跖点的顶点而获得的图，即距离为 n（Q_n 的图直径）。 Brouwer 等人 1989 年（第 222 页）使用符号 square _k 表示折叠 k-立方体图。

对于 n>2，折叠 n-立方体图是 正则 的，度数为 n。它有 2^(n-1) 个顶点，2^(n-2)n 条边，直径为 |_n/2_|。色数当 n 为偶数时为 2，当 n 为奇数时为 4 (Godsil 2004)。 Godsil 观察到，折叠 n-立方体图 F_n 的独立数由下式给出

alpha(F_n)=2^(n-2)-1/4(1-(-1)^n)(n-1; (n-1)/2),

这个结果来自于 Cvetkovic 的特征值界，用于建立上限，并通过观察当 n 为奇数（或偶数）时，与固定顶点距离为奇数（或偶数）的顶点来直接构造独立集（S. Wagon, 私人通讯）。

折叠立方体图是距离正则和距离传递的。

下表总结了特殊情况。

n折叠 n-立方体图
22-路径图 P_2
3四面体图 K_4
4完全二部图 K_(4,4)
5Clebsch 图
6Kummer 图

折叠 n-立方体图的二部双图是超立方体图 Q_n。

参见

Clebsch 图, 半立方体图, 超立方体图, Kummer 图

使用 Wolfram|Alpha 探索

参考文献

Brouwer, A. E. "Folded 6-Cube and Graphs with the Same Parameters." http://www.win.tue.nl/~aeb/drg/graphs/Folded-6-cube.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "Halved and Folded Cubes." §9.2D in Distance-Regular Graphs. New York: Springer-Verlag, pp. 264-265, 1989.Choudam, S. A. and Nandini, R. U. "Complete Binary Trees in Folded and Enhanced Cubes." Networks 43, 266-272, 2004.DistanceRegular.org. "Folded Cubes." http://www.distanceregular.org/indexes/foldedcubes.html.El-Amawy, A. and Latifi, S. "Properties and Performance of Folded Hypercubes." IEEE Trans. Parallel Distrib. Syst. 2, 31-42, 1991.Godsil, C. "Folded Cubes" and "Eigenvalues and Folded Cubes." §7.6 and 7.7 in Interesting Graphs and Their Colourings. Unpublished manuscript, pp. 70-73, 2006.van Bon, J. "Finite Primitive Distance-Transitive Graphs." Europ. J. Combin. 28, 517-532, 2007.van Dam, E. and Haemers, W. H. "An Odd Characterization of the Generalized Odd Graphs." CentER Discussion Paper Series, No. 2010-47, SSRN 1596575. 2010.Varvarigos, E. "Efficient Routing Algorithms for Folded-Cube Networks." Proc. 14th Int. Phoenix Conf. on Computers and Communications. IEEE, pp. 143-151, 1995.

在 Wolfram|Alpha 上被引用

折叠立方体图

引用为

Weisstein, Eric W. "Folded Cube Graph." 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/FoldedCubeGraph.html

主题分类