轮图

{{infobox graph
| name = 轮图
| image =
| image_caption = 轮图的一些例子
| girth = 3
| diameter = 2，如果n > 4
1，如果n = 4
| vertices = n
| edges = 2(n − 1)
| chromatic_number = 4，如果n是偶数
3，如果n是奇数
| chromatic_index =
| spectrum = \{2\cos(2k\pi / (n - 1))^1;
k = 1, \ldots, n - 2\}\cup\{1 \pm \sqrt{n}\}
| properties = 哈密顿图
自对偶
平面图
| notation = Wn
}}

在图论这一数学分支中，轮图（）是指一个完全点连接到一个循环图上所有节点而形成的图。一些文献中会使用记号Wn来表示有n个节点（n ≥ 4）的轮图；另一些文献中则使用Wn来表示有n+1个节点（n ≥ 3）的轮图，这里n是指形成轮图的循环图中节点的数量。在本条目中使用前一种记号。

构造
给定一个点集{1, 2, 3, …, v}，则若使用集合建构式符号，轮图的边集可以表示为{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}}。

性质
轮图是平面图，因此有唯一的平面嵌入。更进一步，每个轮图都是。轮图是自对偶的：轮图的平面对偶和其自身同构。除了K4 = W4之外，每个极大平面图都有一个形如W5或W6的子图。

任意轮图中总有哈密顿环。Wn中有n^2-3n+3个环。

当n为奇数时，Wn是一个，其色数为3：环上的节点可以用两种颜色染色，而中间的完全点使用第三种颜色。当n为偶数时，Wn的色数为4，且当n ≥ 6时不是完美图。W7是轮图中在欧几里得平面上的唯一一个单位距离图。

轮图Wn的色多项式为P_{W_n}(x) = x((x - 2)^{(n - 1)} - (-1)^n(x - 2))。

在拟阵论中，两类重要的拟阵轮拟阵（）和旋拟阵（）的概念都是轮图的推广。

轮图W6是埃尔德什·帕尔对拉姆齐理论一个猜想的反例：他猜想在色数相同的图中，完全图的拉姆齐数是最小的。但后来有研究发现W6的拉姆齐数是17，而与之色数相同的完全图K4的拉姆齐数则是18。也就是说，对于任意17节点的图G，G或它的补图一定有子图W6；而17节点的和它的补图都没有子图K4。

参考资料