高度不规则图

如果一个连通图中每个顶点的邻居都具有不同的顶点度，则称该图为高度不规则图。高度不规则图存在于除 3、5 和 7 之外的所有阶数上，节点数为 1, 2, ... 的此类图的数量由 1, 1, 0, 1, 0, 1, 0, 3, 3, 13, 21, 110, 474, 2545, ... 给出 (OEIS A217246)。

上面的小例子说明了每个节点的顶点度，并在下表中进行了总结。

顶点计数	高度不规则图
1	单例图
2	路径图
4	路径图
6	一个图
8	4-蜈蚣图

上面说明了 和 9 个节点上的更大示例，同样标记了每个节点的顶点度。

高度不规则图是顶点、桥和非哈密顿的。

如果 是一个具有最大顶点度 的顶点，在一个高度不规则图中，那么 正好与一个度为 1, 2, ..., 的顶点相邻 (Alavi et al. 2022)。

在 个顶点的高度不规则图中，最大顶点度最多为 (Alavi et al. 2022)。