主題
Search

格林伯格圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
GrinbergGraphs

格林伯格構造了許多小的立方多面體圖，這些圖是泰特哈密頓圖猜想（即，每個 3 連通立方圖都是哈密頓圖）的反例。這些非哈密頓圖都與格林伯格的名字相關聯，其中 44 頂點的例子被稱為“格林伯格圖”（Read 和 Wilson 1998, p. 274），而 46 頂點的例子被稱為“格林伯格圖”（Bondy 和 Murty 1976, p. 162; Thomassen 1981）。44 頂點圖是最小的 3 價、平面、3 連通、迴圈 5 連通的非哈密頓圖 (Grünbaum 1974)。

從上圖可以看出，42 頂點圖可以透過刪除 44 頂點圖頂部中間部分的單條邊來得到（Faulkner 和 Younger 1974）。根據 Zamfirescu (1976) 的說法，44 頂點圖是由 Grinberg (1968) 和 Tutte (Grünbaum 1970, Faulkner 和 Younger 1974) 獨立發現的。

GrinbergGraphEmbeddings

上圖展示了 42 頂點和 44 頂點格林伯格圖的更多嵌入。

後來發現了更小的 3 連通立方非哈密頓圖，有 38 個頂點（Barnette-Bosák-Lederberg 圖）。Faulkner-Younger 圖是另一對 3 連通立方非哈密頓圖，分別有 42 個和 44 個頂點，它們像格林伯格圖一樣，透過刪除單條邊相互關聯。

另請參閱

Barnette-Bosák-Lederberg 圖, Faulkner-Younger 圖, 非哈密頓圖, 泰特哈密頓圖猜想, Tutte 圖

使用 探索

參考文獻

Berge, C. 圖與超圖。 New York: Elsevier, 1973.Bondy, J. A. and Murty, U. S. R. Fig. 9.27 in 圖論及其應用。 New York: North Holland, p. 162, 1976.Faulkner, G. B. and Younger, D. H. "非哈密頓立方平面圖。" Discr. Math. 7, 67-74, 1974.Grinberg, E. J. "沒有哈密頓迴路的 3 度平面均勻圖。" Latvian Math. Yearbook, Izdat. Zinatne, Riga 4, 51-58, 1968.Grünbaum, B. "多面體、圖與復形。" Bull. Amer. Math. Soc. 76, 1131-1201, 1970.Grünbaum, B. "最長路徑或迴路遺漏的頂點。" J. Combin. Th. A 17, 31-38, 1974.Read, R. C. and Wilson, R. J. 圖譜。 Oxford, England: Oxford University Press, p. 274, 1998.Sachs, H. "Kozyrev 和 Grinberg 指出的非哈密頓立方平面圖。" In Beiträge zur Graphentheorie. Leipzig, Germany: Teubner, pp. 127-130, 1968.Thomassen, C. "平面立方次哈密頓和次可追蹤圖。" J. Comb. Th. B 30, 36-44, 1981.Zamfirescu, T. "關於圖中最長路徑和迴路。" Math. Scand. 38, 211-239, 1976.

在 中引用

格林伯格圖

引用為

Weisstein, Eric W. "格林伯格圖。" 來自 Web 資源。 https://mathworld.tw/GrinbergGraphs.html

主題分類