# 立方图

## 对称性

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

## 参考文献

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. ^
8. ^ Gebauer, H., On the number of Hamilton cycles in bounded degree graphs, Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), 2008.