高度不規則圖

如果一個連通圖中每個頂點的鄰居都具有不同的頂點度，則稱該圖為高度不規則圖。高度不規則圖存在於除 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)。