主题
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-部图, 冠图, 手套问题, 握手问题, 梯子图, 聚会问题, 图兰图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上引用

鸡尾酒会图

请引用本文为

Weisstein, Eric W. "鸡尾酒会图。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/CocktailPartyGraph.html

主题分类