Barnette-Bosák-Lederberg 图

Barnette-Bosák-Lederberg 图是一个具有 38 个顶点的图，它是已知的最小的平面 3-连通非哈密顿图的例子，即，Tait 哈密顿图猜想已知的最小反例。它由 Lederberg (1965) 发现，显然 D. Barnette 和 J. Bosák 也在同一时间发现了它。上面分别展示了 Read 和 Wilson (1998) 以及 Grünbaum (2003, p. 361) 给出的两种嵌入方式。

Barnette-Bosák-Lederberg 图在 Wolfram 语言中实现为GraphData["BarnetteBosakLederbergGraph"].

上面的图显示了 Barnette-Bosák-Lederberg 图的邻接、关联和图距离矩阵。

下表总结了 Barnette-Bosák-Lederberg 图的一些属性。

属性	值
自同构群阶数	2
色数	3
色多项式	?
无爪	否
团数	2
由谱确定	否
直径	9
距离正则图	否
边色数	3
边连通度	3
边数	57
边传递	否
欧拉图	否
面数	21
图亏格	0
围长	4
哈密顿图	否
哈密顿路径计数	?
次哈密顿图	否
次可迹图	否
积分图	否
独立数	16
线图	否
完美匹配图	否
平面图	是
多面体图	是
半径	5
正则图	是
无平方	否
对称	否
可迹图	是
无三角形图	是
顶点连通度	3
顶点数	38
顶点传递	否
弱正则参数	(38,(3),(0),(0,1,2))

另请参阅

三次非哈密顿图, Tait 哈密顿图猜想

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Grünbaum, B. Fig. 17.1.5 in Convex Polytopes, 2nd ed. New York: Springer-Verlag, p. 361, 2003.Lederberg, J. "DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs." Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf.Pegg, E. Jr. "The Icosian Game, Revisited." Mathematica J. 11, 310-314, 2009.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 274, 1998.Thomassen, C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb. Th. B 30, 36-44, 1981.

请引用为

Weisstein, Eric W. "Barnette-Bosák-Lederberg 图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Barnette-Bosak-LederbergGraph.html