立方图

彼得森图是立方图

完全二分图 $K_{3,3}$是立方二分图

在图论中，若一个图的每个顶点度数均为三，则称其为立方图（Cubic graph）、3-正则图或三次图。

彼得森图、汤玛森图等都是立方图。

对称性

1932年，Template:Link-en首先寻找立方Template:Link-en的例子，并收集为Template:Link-en。许多著名的图都是立方对称图，如汤玛森图、彼得森图等。威廉·湯瑪斯·圖特用满足下列性质的最大整数s来对立方对称图进行分类：图的自同构群在其所有长度为s的路径（其中不能有重复的边）组成的集合上作用是传递的。他证明了s最大只能取5，也即s的可能值是1到5。

图着色与独立集

根据布鲁克定理，除了K₄以外的任何连通立方图都可以用至多三种颜色染色。也即，这样的连通立方图至少存在一个包含n/3个顶点的独立集，其中n是该图的顶点数。

根据Vizing定理，任一立方图的Template:Link-en只能为三或四。3-边着色又称Tait-着色，Tait-着色方式将边集分割为三个完美匹配。根据Template:Tsl每个二分立方图都有一个Tait-着色。

哈密顿回路

关于立方图是否具有哈密顿回路有许多研究。1880年，Template:Link-en猜想任一立方多面体图都有哈密顿回路。1946年，威廉·湯瑪斯·圖特提出了Template:Link-en的反例，有46个点的Template:Link-en。1971年，图特猜想所有的二分立方图都有哈密顿回路。然而Joseph Horton提出了图特猜想的反例，有96个点的Template:Link-en。在这之后，Template:Link-en又提出了两个反例：Template:Link-en。Template:Link-en（目前仍是猜想）将Tait猜想与图特猜想结合起来，称任一二分立方多面体图都有哈密顿回路。当一个立方图有哈密顿回路时，可以使用Template:Link-en简洁地表示。

如果从所有$n$阶立方图中随机选取一个，那么它有相当大概率有哈密顿回路：当$n$趋近于无穷时，这个概率趋近于1。

Template:Link-en猜想任一$n$阶立方图最多有$2^{n/3}$（约等于$1.260^n$）条不同的哈密顿回路，且给出了极限情况下的例子。目前为止，得到证明的最佳估计为$O({1.276}^n)$。

另见

• Template:Link-en

外部連結

• Template:Cite web
• Template:Mathworld
• Template:Mathworld