立方图

图论中,若一个的每个顶点度数均为三,则称其为立方图(Cubic graph)、3-正则图三次图

彼得森图是立方图
完全二分图 是立方二分图

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

对称性编辑

1932年,Ronald M. Foster英语R. M. Foster首先寻找立方对称图英语Symmetric graph的例子,并收集为Foster census英语Foster census[1]许多著名的图都是立方对称图,如汤玛森图彼得森图等。W. T. Tutte英语W. T. Tutte用满足下列性质的最大整数s来对立方对称图进行分类:图的自同构群在其所有长度为s的路径(其中不能有重复的边)组成的集合上作用是传递的。他证明了s最大只能取5,也即s的可能值是1到5。[2]

图着色与独立集编辑

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

根据Vizing定理,任一立方图的边色数英语Edge chromatic number只能为三或四。3-边着色又称Tait-着色,Tait-着色方式将边集分割为三个完美匹配。根据Kőnig's_theorem英语Kőnig%27s_theorem_(graph_theory)每个二分立方图都有一个Tait-着色。

哈密顿回路编辑

关于立方图是否具有哈密顿回路英语Hamiltonian path有许多研究。1880年,P.G. Tait英语Peter Tait (physicist)猜想任一立方多面体图都有哈密顿回路。1946年,W. T. Tutte英语W. T. Tutte提出了Tait猜想英语Tait's conjecture的反例,有46个点的Tutte图英语Tutte graph。1971年,Tutte猜想所有的二分立方图都有哈密顿回路。然而Joseph Horton提出了Tutte猜想的反例,有96个点的Horton图英语Horton graph[3]在这之后,Mark Ellingham英语Mark Ellingham又提出了两个反例:Ellingham–Horton图英语Ellingham–Horton graph[4][5]Barnette猜想英语Barnette's conjecture(目前仍是猜想)将Tait猜想与Tutte猜想结合起来,称任一二分立方多面体图都有哈密顿回路。当一个立方图有哈密顿回路时,可以使用LCF表示法英语LCF notation简洁地表示。

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

David Eppstein英语David Eppstein猜想任一 阶立方图最多有 (约等于 )条不同的哈密顿回路,且给出了极限情况下的例子。[7]目前为止,得到证明的最佳估计为 [8]

另见编辑

参考文献编辑

  1. ^ Foster, R. M., Geometrical Circuits of Electrical Networks, Transactions of the American Institute of Electrical Engineers, 1932, 51 (2): 309–317, doi:10.1109/T-AIEE.1932.5056068 .
  2. ^ Tutte, W. T., On the symmetry of cubic graphs, Can. J. Math., 1959, 11: 621–624, doi:10.4153/CJM-1959-057-2 .
  3. ^ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
  4. ^ Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
  5. ^ Ellingham, M. N.; Horton, J. D., Non-Hamiltonian 3-connected cubic bipartite graphs, Journal of Combinatorial Theory, Series B, 1983, 34 (3): 350–353, doi:10.1016/0095-8956(83)90046-1  已忽略未知参数|doi-access= (帮助).
  6. ^ Robinson, R.W.; Wormald, N.C., Almost all regular graphs are Hamiltonian, Random Structures and Algorithms, 1994, 5 (2): 363–374, doi:10.1002/rsa.3240050209 .
  7. ^ Eppstein, David, The traveling salesman problem for cubic graphs (PDF), Journal of Graph Algorithms and Applications, 2007, 11 (1): 61–81, arXiv:cs.DS/0302030, doi:10.7155/jgaa.00137 .
  8. ^ Gebauer, H., On the number of Hamilton cycles in bounded degree graphs, Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), 2008 .

外部連結编辑