主题
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 图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中引用

格林伯格图

引用为

Weisstein, Eric W. "格林伯格图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/GrinbergGraphs.html

主题分类