主題
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 圖

使用 探索

參考文獻

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.

在 上被引用

摺疊立方體圖

引用為

Weisstein, Eric W. "Folded Cube Graph." 來自 —— 資源。 https://mathworld.tw/FoldedCubeGraph.html

主題分類