主題
Search

Hypotraceable 圖


一個圖 G 是 hypotraceable 圖,如果 G 沒有 哈密頓路徑 (即,它不是一個 可追蹤圖),但是對於每個 v in VG-v 都有一個 哈密頓路徑 (即,是一個 可追蹤圖) (Bondy 和 Murty 1976, p. 61)。

HypotraceableGraphs

不存在節點數少於或等於 10 的 hypotraceable 圖 (E. Weisstein, Dec. 11, 2013)。事實上,在少量頂點上不存在 hypotraceable 圖導致 T. Gallai 推測這種圖不存在。當 Horton 隨後發現一個有 40 個頂點的 hypotraceable 圖時,這個猜想被反駁了 (Grünbaum 1974, Thomassen 1974)。然後 Thomassen (1974) 表明,對於 p=34, 37, 39, 40,以及所有 p>=42,都存在具有 p 個頂點的 hypotraceable 圖。其中最小的是 34 頂點的 Thomassen 圖 (上圖左側;Thomassen 1974;Bondy 和 Murty 1976, pp. 239-240)。

Walter (1969) 給出了一個連通圖的例子,其中最長路徑沒有共同的頂點,hypotraceable 圖也具有此屬性。

平面 hypotraceable 圖是一類特別令人感興趣的圖。


另請參閱

哈密頓連通圖, Hypohamiltonian 圖, 平面 Hypotraceable 圖, Thomassen 圖, 可追蹤圖, Wiener-Araya 圖, Zamfirescu 圖

使用 探索

參考文獻

Araya, M. 和 Wiener, G. "關於三次平面 Hypohamiltonian 和 Hypotraceable 圖。" Elec. J. Combin. 18, 2001. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy, J. A. 和 Murty, U. S. R. 圖論及其應用。 New York: North Holland, pp. 61 和 239-240, 1976.Grotschel, M. "關於單調對稱旅行商問題:Hypohamiltonian/Hypotraceable 圖和麵。" Math. Operations Res. 5, 285-292, 1980.Grünbaum, B. "最長路徑或迴路遺漏的頂點。" J. Combin. Th. A 17, 31-38, 1974.Holton, D. A. 和 Sheehan, J. 彼得森圖。 Cambridge, England: Cambridge University Press, 1993.Jooyandeh, M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.; 和 Zamfirescu, C. T. "40 個頂點上的平面 Hypohamiltonian 圖。" J. Graph Th. 84, 121-133, 2017.Kapoor, S. F.; Kronk, H. V.; 和 Lick, D. R. "關於圖中的繞行。" Canad. Math. Bull. 11, 195-201, 1968.Thomassen, C. "Hypohamiltonian 和 Hypotraceable 圖。" Disc. Math. 9, 91-96, 1974.Walter, H. "關於圖中所有最長路徑都不經過某個頂點的非存在性。" J. Combin. Th. 6, 1-6, 1969.Wiener, G. 和 Araya, M. "終極問題。" 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener, G. 和 Araya, M. "關於平面 Hypotraceable 圖。" J. Graph Th. 67, 55-68, 2011.

在 中被引用

Hypotraceable 圖

請引用為

Weisstein, Eric W. "Hypotraceable 圖。" 來自 --一個 資源。 https://mathworld.tw/HypotraceableGraph.html

主題分類