TOPICS
Search

Highly Irregular Graph


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).

HighlyIrregularGraphs

Small examples are illustrated above with the vertex degree of each node labeled and summarized in the following table.

vertex counthighly irregular graphs
1singleton graph
2path graph P_2
4path graph P_4
6A graph
84-centipede graph
HighlyIrregularGraphs89

Larger examples on n=8 and 9 nodes are illustrated above, again with the vertex degree of each node labeled.

Highly irregular graphs are apex, bridges, and nonhamiltonian.

If v is a vertex with maximum vertex degree d in a highly irregular graph, then v is adjacent to exactly one vertex of degree 1, 2, ..., d (Alavi et al. 2022).

The maximum vertex degree in a highly irregular graph on n vertices is at most |_n/2_| (Alavi et al. 2022).


See also

Irregular Graph, Regular Graph, Vertex Degree

Explore with Wolfram|Alpha

References

Alavi, Y.; Chartrand, G.; Chung, F. R. K.; Erdö s, P.; Graham, R. L.; and Oellermann, O. R. "Highly Irregular Graphs." J. Graph Th. 11, 235-249, 1987.Sloane, N. J. A. Sequence A217246 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Highly Irregular Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HighlyIrregularGraph.html

Subject classifications