Halin 图

Halin 图，有时被称为无顶多面体，是由具有四个或更多顶点、没有度数为 2 的顶点，并且通过将树的所有叶子与绕树边界传递的循环连接而构造的树的平面嵌入构造的多面体图。 Halin 图的例子包括轮图 、三角形棱柱图 和 Frucht 图。 上面说明了这些以及 Halin 图的其他一些示例。

顶点数为 、2、... 的 Halin 图的数量为 0、0、0、1、1、2、2、4、6、13、22、50、106、252、... (OEIS A346779) (E. Weisstein, 8 月 3 日 - 9 月 29 日，2021 年)。

具有 个顶点和 条边的图是 Halin 图 当且仅当 它是多面体的（即，平面且 3-连通的），并且具有一个面，该面的顶点数等于图的环秩 。

Halin 图是哈密顿图，并且在删除任何单个顶点后仍然是哈密顿图（Cornuéjols等人，1983 年）。 Halin 图的树宽为 3（Bodlaender，1988 年），是非二分图，并且包含三角形（三阶循环）。

第 个 节点 Halin 图对于（至少）以下 值是火柴棍图：（7, 1）（轮图 ）、（10, 3）、（10, 8）、（10, 10）、（11, 18）、（12, 6）、（12, 8）、（12, 10）、（12, 12）、（12, 16）、（12, 17）、（12, 21）、（12, 23）、（12, 30）、（12, 33）和（12, 34）。