A connected graph is said to be highly irregular if the neighbors of each vertex have distinct vertex degrees. Highly irregular graphs exist on all orders except 3, 5 and 7, with the numbers of such graphs on 1, 2, ... nodes given by 1, 1, 0, 1, 0, 1, 0, 3, 3, 13, 21, 110, 474, 2545, ... (OEIS A217246).
Small examples are illustrated above with the vertex degree of each node labeled and summarized in the following table.
vertex count | highly irregular graphs |
1 | singleton graph |
2 | path graph |
4 | path graph |
6 | A graph |
8 | 4-centipede graph |
Larger examples on and 9 nodes are illustrated above, again with the vertex degree of each node labeled.
Highly irregular graphs are apex, bridges, and nonhamiltonian.
If is a vertex with maximum vertex degree in a highly irregular graph, then is adjacent to exactly one vertex of degree 1, 2, ..., (Alavi et al. 2022).
The maximum vertex degree in a highly irregular graph on vertices is at most (Alavi et al. 2022).