主题
Search

超哈密顿图

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

如果图 G 是非哈密顿图，但对于每个 v in V 中的 G，G-v 都是哈密顿图，则称图 G 为超哈密顿图（Bondy 和 Murty 1976，页 61）。Petersen 图有十个节点，是最小的超哈密顿图（Herz等人1967；Bondy 和 Murty 1976，页 61），也是十个节点上唯一的此类图。Herz等人（1967）表明，不存在具有 11 或 12 个顶点的超哈密顿图。

根据奇偶性，没有二部图是超哈密顿图。许多（但不是全部）snarks是超哈密顿图。

超哈密顿图是近哈密顿图。

Zamfirescu（2019）表明，每个单交叉超哈密顿图都包含一个三次顶点（Tsai 2024）。

HypohamiltonianFamily6

Lindgren-Sousselier 图是由 Sousselier（在 Herz等人1967 年）和 Lindgren（1967 年）独立构建的顶点数为 6k+10 的超哈密顿图序列。

Bondy（1972）发现了顶点数为 12k+10 的超哈密顿图的无限序列。

Sousselier 发现了一个 18 个顶点的三次超哈密顿图（Chvátal 1973）。Chvátal（1973）表明，对于每个 p>=26，都存在一个顶点数为 p 的超哈密顿图。更一般地，对于每个 p>=13，都存在一个超哈密顿图，但 p=14（Collier 和 Schmeichel 1978）和 p=17（Aldred等人1997）除外。Aldred等人（1997）给出了所有（七个）顶点数小于等于 17 的超哈密顿图的完整枚举。McKay 给出了所有已知的顶点数不超过 26 的超哈密顿图的列表（其中顶点数大于等于 18 的枚举可能不完整），以及一个周长受限的顶点数不超过 26 的三次超哈密顿图的子集。顶点数为 n=1, 2, ... 的超哈密顿图的数量为 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 4, 0, 14, 34, ... （OEIS A141150；Goedgebeur 和 Zamfirescu 2017）。

Thomassen（1973）发现了顶点数为 p=20 和 25 的超哈密顿图，Collier 和 Schmeichel（1978）发现了顶点数为 p=18 和 22 的“新”超哈密顿图，尽管他们“新”的 p=18 图实际上与第一个 Blanuša snark 同构，而他们“新”的 p=22 图与 Loupekine snarks 同构。

HypohamiltonianGraphs

上面显示了一些非 snark 超哈密顿图，包括一些先前讨论过的，按顶点数排序。

平面超哈密顿图是一类特别受关注的次可迹图（Jooyandeh等人2017）。

下表总结了一些顶点数不超过 50 的命名超哈密顿图（包括 snarks）。

图 G|V(g)|平面的
Petersen 图10N
Sousselier 图16N
第一个和第二个 Blanuša snarks18N
flower snark J_520N
20-Thomassen 图20N
第一个和第二个 Loupekine snarks22N
广义 Petersen 图 P_(11,2)22N
第一个和第二个 Celmins-Swart snarks26N
Coxeter 图28N
flower snark J_728N
double star snark30N
32-Thomassen 图32N
广义 Petersen 图 GP(17,2)34N
Wiener-Araya 图42Y
48-Zamfirescu 图48Y
Szekeres snark50N

另请参阅

近哈密顿图, 近超哈密顿图, Araya-Wiener 图, 三次平面超哈密顿图, 哈密顿图, Hatzel 图, 次可迹图, Lindgren-Sousselier 图, Petersen 图, 平面超哈密顿图, Snark, 可迹图, Wiener-Araya 图, Zamfirescu 图

使用 Wolfram|Alpha 探索

参考文献

Aldred, R. E. L.; Bau, S.; Holton, D. A.; and McKay, B. D. "Nonhamiltonian 3-Connected Cubic Planar Graphs." SIAM J. Disc. Math. 13, 25-32, 2000.Aldred, R. E. L.; McKay, B. D.; and Wormald, N. C. "Small Hypohamiltonian Graphs." J. Combin. Math. Combin. Comput. 23, 143-152, 1997.Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin. 18, 2011. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy, J. A. "Variations of the Hamiltonian Theme." Canad. Math. Bull. 15, 57-62, 1972.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, 页 61, 1976.Chvátal, V. "Flip-Flops in Hypohamiltonian Graphs." Canad. Math. Bull. 16, 33-41, 1973.Collier, J. B. and Schmeichel, E. F. "Systematic Searches for Hypohamiltonian Graphs." Networks 8, 193-200, 1978.Doyen, J. and van Diest, V. "New Families of Hypohamiltonian Graphs." Disc. Math. 13, 225-236, 1975.Gaudin, T.; Herz, J.-C.; and Rossi, P. "Solution de problème no. 29." Française Informat. Recherche Opérationnelle 8, 214-218, 1964.Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, 页 66, 2001.Goedgebeur, J. and Zamfirescu, C. T. "Improved Bounds for Hypohamiltonian Graphs." Ars Math. Contemp. 13, 235-257, 2017.Grotschel, M. "On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets." Math. Operations Res. 5, 285-292, 1980.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Hatzel, H. "Ein planarer hypohamiltonscher Graph mit 57 Knoten." Math Ann. 243, 213-216, 1979.Herz, J. C.; Duby, J. J.; and Vigué, F. "Recherche systématique des graphes hypohamiltoniens." 在 Theory of Graphs: Internat. Sympos., Rome 1966 (Ed. P. Rosenstiehl). Paris: Gordon and Breach, 页 153-159, 1967.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.House of Graphs. "Hypohamiltonian Graphs." https://houseofgraphs.org/meta-directory/hypohamiltonian.Jooyandeh, M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.; and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices." J. Graph Th. 84, 121-133, 2017.Katerinis, P. "Some Properties of Hypohamiltonian Graphs." Aeq. Math. 72, 139-151, 2006.Lindgren, W. F. "An Infinite Class of Hypohamiltonian Graphs." Amer. Math. Monthly 74, 1087-1089, 1967.McKay, B. "Hypohamiltonian Graphs." http://cs.anu.edu.au/~bdm/data/graphs.html.Skupień, Z. "Exponentially Many Hypohamiltonian Snarks." Electronic Notes in Disc. Meth. 28, 417-424, 2007.Sloane, N. J. A. Sequence A141150 in "The On-Line Encyclopedia of Integer Sequences."Sousselier, R. "Problème no. 29: Le cercle des irascibles." Rev. Franc. Rech. Operat. 7, 405-406, 1963.Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs." Disc. Math. 9, 91-96, 1974.Thomassen, C. "On Hypohamiltonian Graphs." Disc. Math. 10, 383-390, 1974.Thomassen, C. "Planar and Infinite Hypohamiltonian and Hypotraceable Graphs." Disc. Math 14, 377-389, 1976.Thomassen, C. "Hypohamiltonian Graphs and Digraphs." 在 Theory and Applications of Graphs Proceedings, Michigan May 11-15, 1976 (Ed. Y. Alavi and D. R. Lick). New York: Springer-Verlag, 页 557-571, 1978.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb. Th. B 30, 36-44, 1981.Tsai, C.-C. "Small Planar Hypohamiltonian Graphs." 8 Apr 2024. https://arxiv.org/abs/2403.18384.Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener, G. and Araya, M. "On Planar Hypohamiltonian Graphs." J. Graph Th. 67, 55-68, 2011.Zamfirescu, C. T. and Zamfirescu, T. I. "A Planar Hypohamiltonian Graph with 48 Vertices." J. Graph Th. 48, 338-342, 2007.Zamfirescu, C. T. "Cubic Vertices in Planar Hypohamiltonian Graphs." J. Graph Th. 90, 189-207, 2019.

在 Wolfram|Alpha 中被引用

超哈密顿图

引用为

Weisstein, Eric W. “超哈密顿图。” 来自 MathWorld—— Wolfram 网络资源。 https://mathworld.net.cn/HypohamiltonianGraph.html

主题分类