Graph irregularity and its measures

摘要

Let G be a simple graph. If all vertices of G have equal degrees, then G is said to be regular. Otherwise, G is irregular. There were various attempts to quantify the irregularity of a graph, of which the Collatz–Sinogowitz index, Bell index, Albertson index, and total irregularity are the best known. We now show that no two of these irregularity measures are mutually consistent, namely that for any two such measures, irrX and irrY there exist pairs of graphs G1, G2, such that irrX(G1) > irrX(G2) but irrY(G1) < irrY(G2). This implies that the concept of graph irregularity is not free of ambiguities.