主題
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 圖

使用 探索

參考文獻

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.

在 中被引用

超哈密頓圖

引用為

Weisstein, Eric W. “超哈密頓圖。” 來自 —— Wolfram 網路資源。 https://mathworld.tw/HypohamiltonianGraph.html

主題分類