Group for Research in Decision Analysis


Variable Neighborhood Search for Extremal Graphs 9. Bounding the Irregularity of a Graph


Albertson (1997) defines the imbalance of an edge (i,j) in E of a graph G = (V,E) as | di - dj | where dj is the degree of a vertex j in V, and the irregularity irr(G) of G as the sum of imbalances of its edges. Exploiting conjectures of the system AutoGraphiX, an upper bound on irr(G) is derived, which is tight for all numbers n = |V| and m = |E| of vertices and edges compatible with the existence of a graph. Extremal graphs are shown to be fanned split graphs, i.e., complete split graphs with the possible addition of edges all incident with the same vertex.

, 16 pages

This cahier was revised in January 2003