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]
David Eppstein（英语：David Eppstein）猜想任一阶立方图最多有（约等于）条不同的哈密顿回路，且给出了极限情况下的例子。[7]目前为止，得到证明的最佳估计为。[8]
另见
一些简单的立方图（英语：Table of simple cubic graphs）
参考文献
^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.
^Tutte, W. T., , Can. J. Math., 1959, 11: 621–624 [2019-05-10], doi:10.4153/CJM-1959-057-2, （原始内容存档于2011-07-16）.
^Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
^Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
^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.
^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.
^Eppstein, David, (PDF), Journal of Graph Algorithms and Applications, 2007, 11 (1): 61–81 [2020-12-27], arXiv:cs.DS/0302030, doi:10.7155/jgaa.00137, （原始内容 (PDF)存档于2021-02-24）.
^Gebauer, H., On the number of Hamilton cycles in bounded degree graphs, Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), 2008.
立方图, 此條目可参照英語維基百科相應條目来扩充, 2019年4月23日, 若您熟悉来源语言和主题, 请协助参考外语维基百科扩充条目, 请勿直接提交机械翻译, 也不要翻译不可靠, 低品质内容, 依版权协议, 译文需在编辑摘要注明来源, 或于讨论页顶部标记, href, template, translated, page, html, title, template, translated, page, translated, page, 标签, 在图论中, 若一个图的每个顶点度数均为三, 则称其为, cubic,. 此條目可参照英語維基百科相應條目来扩充 2019年4月23日 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 在图论中 若一个图的每个顶点度数均为三 则称其为立方图 Cubic graph 3 正则图或三次图 彼得森图是立方图 完全二分图 K 3 3 displaystyle K 3 3 是立方二分图 彼得森图 汤玛森图等都是立方图 目录 1 对称性 2 图着色与独立集 3 哈密顿回路 4 另见 5 参考文献 6 外部連結对称性 编辑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 着色方式将边集分割为三个完美匹配 根据Konig s theorem 英语 Konig 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 简洁地表示 如果从所有n displaystyle n 阶立方图中随机选取一个 那么它有相当大概率有哈密顿回路 当n displaystyle n 趋近于无穷时 这个概率趋近于1 6 David Eppstein 英语 David Eppstein 猜想任一n displaystyle n 阶立方图最多有2 n 3 displaystyle 2 n 3 约等于1 260 n displaystyle 1 260 n 条不同的哈密顿回路 且给出了极限情况下的例子 7 目前为止 得到证明的最佳估计为O 1 276 n displaystyle O 1 276 n 8 另见 编辑一些简单的立方图 英语 Table of simple cubic graphs 参考文献 编辑 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 Tutte W T On the symmetry of cubic graphs Can J Math 1959 11 621 624 2019 05 10 doi 10 4153 CJM 1959 057 2 原始内容存档于2011 07 16 Bondy J A and Murty U S R Graph Theory with Applications New York North Holland p 240 1976 Ellingham M N Non Hamiltonian 3 Connected Cubic Partite Graphs Research Report No 28 Dept of Math Univ Melbourne Melbourne 1981 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 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 Eppstein David The traveling salesman problem for cubic graphs PDF Journal of Graph Algorithms and Applications 2007 11 1 61 81 2020 12 27 arXiv cs DS 0302030 doi 10 7155 jgaa 00137 原始内容 PDF 存档于2021 02 24 Gebauer H On the number of Hamilton cycles in bounded degree graphs Proc 4th Workshop on Analytic Algorithmics and Combinatorics ANALCO 08 2008 外部連結 编辑Royle Gordon Cubic symmetric graphs The Foster Census 原始内容存档于2011 10 23 埃里克 韦斯坦因 Bicubic Graph MathWorld 埃里克 韦斯坦因 Cubic Graph MathWorld 取自 https zh wikipedia org w index php title 立方图 amp oldid 72622861, 维基百科，wiki，书籍，书籍，图书馆，
