轮图

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

轮图
轮图的一些例子
顶点	n
边	2(n − 1)
直径	2，如果n > 4 1，如果n = 4
围长	3
色数	4，如果n是偶数 3，如果n是奇数
属性	哈密顿图 自对偶 平面图

构造

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

性质

轮图是平面图，因此有唯一的平面嵌入。更进一步，每个轮图都是哈林图（英语：Halin graph）。轮图是自对偶的：轮图的平面对偶和其自身同构。除了K₄ = W₄之外，每个极大平面图都有一个形如W₅或W₆的子图。

任意轮图中总有哈密顿环。W_n中有${\displaystyle n^{2}-3n+3}$个环（OEIS数列A002061）。

轮图W₄中的7个环

当n为奇数时，W_n是一个完美图（英语：perfect graph），其色数为3：环上的节点可以用两种颜色染色，而中间的完全点使用第三种颜色。当n为偶数时，W_n的色数为4，且当n ≥ 6时不是完美图。W₇是轮图中在欧几里得平面上的唯一一个单位距离图（英语：unit distance graph）^[4]。

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

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

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