可追踪图

可追踪图是具有图，它拥有哈密顿路径。哈密顿图因此是可追踪的，但反之不一定成立。不可追踪的图被称为不可追踪。

当 , 2, ... 时，可追踪图的数量为 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864)，其中，按照惯例，单点图被认为是可追踪的。上面展示了前几个图，每个图的哈密顿路径都用橙色标出。

每个自补图都是可追踪的 (Clapham 1974; Camion 1975; Farrugia 1999, p. 52)。

维网格图，具有任意形状和维度，似乎都是可追踪的，尽管在文献中似乎没有完全证明这一论断（参见 Simmons 1978, Hedetniemi et al. 1980, Itai et al. 1982, Zamfirescu and Zamfirescu 1992）。

下表列出了一些可追踪但不是哈密顿图的著名图。

图
theta-0 图	7
彼得森图	10
赫舍尔图	11
Blanuša snarks	18
flower snark	20
考克斯特图	28
double star snark	30
Tutte 图	46
Szekeres snark	50
McLaughlin 图	276

另请参阅

欧拉回路, 哈密顿连通图, 哈密顿图, 次可追踪图, 柯尼斯堡七桥问题, 洛瓦兹猜想, 单笔画回路, 不可追踪图

使用探索

更多尝试

参考文献

Camion, P. "自补图中的哈密顿链。" 收录于 图论研讨会（巴黎，1974 年） (Ed. P. P. Gillis and S. Huyberechts). 布鲁塞尔运筹学研究中心学报 17, pp. 173-183, 1975.Clapham, C. R. J. "自补图中的哈密顿弧。" Disc. Math. 8, 251-255, 1974.Farrugia, A. "自补图及其推广：综合参考手册。" 8 月 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Godsil, C. 和 Royle, G. "哈密顿路径和环。" C§3.6 收录于 代数图论。 纽约: 施普林格出版社, pp. 45-47, 2001.Gould, R. J. "哈密顿问题更新——综述。" J. Graph Th. 15, 121-157, 1991.Hedetniemi, S. M.; Hedetniemi, S. T.; 和 Slater, P. S. "哪些网格是哈密顿图？" Congr. Numer. 29, 511-524, 1980.Itai, A.; Papadimitriou, C. H.; 和 Szwarcfiter, J. L. "网格图中的哈密顿路径。" SIAM J. Comput. 11, 676-686, 1982.Mütze, T. "关于由相交集系统定义的图中的哈密顿环。" Not. Amer. Soc. 74, 583-592, 2024.Simmons, G. J. "几乎所有

维矩形格子都是哈密顿可编织的。" 收录于 第九届东南组合数学、图论和计算会议论文集（佛罗里达大西洋大学，博卡拉顿，佛罗里达州，1978 年） (Ed. F. Hoffman, D. McCarthy, R. C. Mullin, and R. G. Stanton). 温尼伯，马尼托巴: Utilitas Mathematica Publishing, pp. 649-661, 1978.Sloane, N. J. A. “整数序列在线百科全书”中的序列 A057864。Thomassen, C. "次哈密顿图和次可追踪图。" Disc. Math. 9, 91-96, 1974.Zamfirescu, C. 和 Zamfirescu, T. "网格图的哈密顿性质。" SIAM J. Disc. Math. 5, 564-570, 1992.