主題
Search

平面次可跡圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook
PlanarHypotraceableGraphs

平面次可跡圖是一個次可跡圖，同時也是平面圖。上面展示了一些平面次可跡圖。

根據 Thomassen (1974) 的一個定理，具有 42 個頂點的 Wiener-Araya 圖 可以用來構造一個具有 162 個頂點的平面次可跡圖，這比使用 Thomassen 構造從 48-Zamfirescu 圖 獲得的 186 頂點圖要小。這些圖在 Wolfram 語言 中實現為GraphData[{"PlanarHypohamiltonian", 162}] 和GraphData[{"PlanarHypohamiltonian", 186}]， 分別為。

Jooyandeh 等人 (2017) 表明，存在具有 154 個頂點的平面次可跡圖，以及所有頂點數大於或等於 156 的平面次可跡圖。

使用 70 節點的 Araya-Wiener 圖，可以構造一個 340 節點的立方平面次可跡圖 (Araya 和 Wiener 2011)。

Holton 和 Sheehan (1993) 詢問是否存在一個整數 n，使得對於每個偶數 >=n 都存在立方平面次可跡圖，而 Araya 和 Wiener (2011) 用 n=356 回答了這個問題。

另請參閱

哈密頓連通圖, 次可跡圖, 平面圖, 平面次哈密頓圖, Thomassen 圖, 可跡圖, Wiener-Araya 圖, Zamfirescu 圖

使用 探索

參考文獻

Araya, M. 和 Wiener, G. "關於立方平面次哈密頓圖和次可跡圖." 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. "關於單調對稱旅行商問題：次哈密頓/次可跡圖和麵." 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 個頂點的平面次哈密頓圖." 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. "次哈密頓圖和次可跡圖." Disc. Math. 9, 91-96, 1974.Walter, H. "Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen." J. Combin. Th. 6, 1-6, 1969.Wiener, G. 和 Araya, M. "終極問題." 2009 年 4 月 20 日. http://arxiv.org/abs/0904.3012.Wiener, G. 和 Araya, M. "關於平面次可跡圖." J. Graph Th. 67, 55-68, 2011.

請引用為

韋斯坦因，埃裡克·W. "平面次可跡圖。" 來自 —— 資源。 https://mathworld.tw/PlanarHypotraceableGraph.html

主題分類