主题
Search

轮图

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook
WheelGraphs

如本文所定义，轮图 W_n，有时简称为 n-轮（Harary 1994, p. 46; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 78），是一个包含 圈 且阶数为 n-1 的图，其中圈中的每个图顶点都连接到另一个称为中心顶点的图顶点。 包含中心顶点的轮的边称为辐条 (Skiena 1990, p. 146)。 轮图 W_n 可以定义为图的连接 K_1+C_(n-1)，其中 K_1 是单点图，C_n 是圈图，使其成为 (n,1)-锥图。 上面展示了 4 到 8 阶轮图的一些嵌入方式。

请注意，一些作者（例如 Gallian 2007）采用了另一种约定，其中 W_n 表示在 n+1 节点上的轮图。

四面体图（即，K_4）与 W_4 同构，而 W_5 与完全三部图 K_(1,2,2) 同构。 一般来说，n-轮图是 (n-1)-棱锥的骨架。

轮图 W_n 与 Jahangir 图 J_(1,n-1) 同构。

W_5 是从五胞体图 K_5 中移除两条边得到的两个图之一，另一个是房屋 X 图。

W_5 是一个准正则图。

轮图是优美的、自对偶的、泛圈的和支配唯一的。

对于 n=7，轮图 W_n 的图的维数为 2（因此是单位距离图），否则维数为 3（因此不是单位距离图）（Erdős et al. 1965, Buckley 和 Harary 1988）。

轮图可以使用以下 Wolfram 语言构造：WheelGraph[n]。 预计算的轮图属性可以通过以下方式获得GraphData[{"Wheel", n}].

WheelGraphCycles4
WheelGraphCycles5

轮图 W_n 中的图圈数由 n^2-3n+3 给出，或者对于 n=4, 5, ... 为 7、13、21、31、43、57、...（OEIS A002061）。

在轮图中，中心顶点的度为 n-1，其他节点的度为 3。 轮图是 3-连通的。 W_4=K_4，其中 K_4 是四阶完全图。 W_n 的色数是

chi(W_n)={3 for n odd; 4 for n even.
(1)

轮图 W_n 有色多项式

pi(x)=x[(x-2)^(n-1)-(-1)^n(x-2)].
(2)

另请参阅

完全图, 锥图, 双棱锥图, 齿轮图, 舵图, 中心顶点, Jahangir 图, 梯形图, 棱锥, 辐条图, Tutte 轮定理, 网状图, 轮补图

使用 Wolfram|Alpha 探索

参考文献

Brandstädt, A.; Le, V. B.; and Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, p. 19, 1987.Buckley, F. and Harary, F. "On the Euclidean Dimension of a Wheel." Graphs and Combin. 4, 23-30, 1988.Frucht, R. "Graceful Numbering of Wheels and Related Graphs." Ann. New York Acad. Sci. 319, 219-229, 1979.Erdős, P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 46, 1994.Pemmaraju, S. and Skiena, S. "Cycles, Stars, and Wheels." §6.2.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 248-249, 2003.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 148, 1986.Skiena, S. "Cycles, Stars, and Wheels." §4.2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 91 and 144-147, 1990.Sloane, N. J. A. Sequence A002061/M2638 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. Graph Theory. Cambridge, England: Cambridge University Press, 2005.

在 Wolfram|Alpha 中被引用

轮图

请引用为

Weisstein, Eric W. "Wheel Graph." 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/WheelGraph.html

主题分类