主題
Search

雞尾酒會圖

下載 Mathematica 筆記本下載 Wolfram 筆記本
CocktailPartyGraph

階數為 n 的雞尾酒會圖，也稱為超八面體圖 (Biggs 1993, p. 17), n-八面體圖 O_n (Jungerman 和 Ringel 1978), 匹配圖 (Arvind et al. 2017), 或 Roberts 圖，是由兩行配對節點組成的圖，其中除配對節點外的所有節點都與圖邊連線。它是圖的補圖 nP_2^_，是梯子橫檔圖 nP_2 的補圖，也是對偶圖 of the 超立方體圖 Q_n。它也是 n-交叉多胞形的骨架（這也是一些作者將其命名為超八面體圖的由來）。

它是完全 n-部圖 K_(2,...,2_()_(n))，也用各種符號表示為 K_(n×2) (例如，Brouwer et al. 1989, pp. 222-223) 和 K_(n(2)) (例如，Stahl 1978; White 2001, p. 59)。

這個圖出現在握手問題中。

雞尾酒會圖是距離傳遞的，因此也是距離正則的。它們也是對蹠的。

階數為 n 的雞尾酒會圖與迴圈圖 Ci_(1,2,...,n-1)(2n) 同構。n-雞尾酒會圖也是 (2n,n)-圖蘭圖。

下表總結了特殊情況。

nn-雞尾酒會圖
1空圖 E_2
2方圖 C_4
3八面體圖
416-胞圖

n-雞尾酒會圖具有獨立多項式

I_n(x)=1+nx(x+2)

具有相應的遞推方程

I_n(x)=2I_(n-1)(x)-I_(n-2)(x).

參見

完全 k-部圖, 冠圖, 手套問題, 握手問題, 梯子圖, 聚會問題, 圖蘭圖

使用 探索

參考文獻

Arvind, V.; Köbler, J.; Rattan, G.; 和 Verbitsky, O. "論顏色細化的力量。" 在 計算理論基礎。FCT 2015 (Ed. A. Kosowski 和 I. Walukiewicz). Cham, Switzerland: Springer, pp. 339-350, 2015.Ball, W. W. R. 和 Coxeter, H. S. M. 數學娛樂與散文，第 13 版。 New York: Dover, p. 278, 1987.Biggs, N. L. 代數圖論，第 2 版。 Cambridge, England: Cambridge University Press, pp. 17 和 68, 1993.Brouwer, A. E.; Cohen, A. M.; 和 Neumaier, A. 距離正則圖。 New York: Springer-Verlag, 1989.Jungerman, M. 和 Ringel, G. "n-八面體的虧格：正則情況。" J. Graph Th. 2, 69-75, 1978.Roberts, F. S. "關於圖的盒度和立方度。" 在 組合數學的最新進展。 New York: Academic Press, pp. 301-310, 1969.Stahl, S. "圖的嵌入--一項調查。" J. Graph Th. 2, 275-298, 1978.White, A. T. "圖論中的嵌入問題。" Ch. 6 在 曲面上的群圖：互動與模型 (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, pp. 49-72, 2001.

在 上引用

雞尾酒會圖

請引用本文為

Weisstein, Eric W. "雞尾酒會圖。" 來自 --一個 資源。 https://mathworld.tw/CocktailPartyGraph.html

主題分類