Highly irregular graph

In graph theory, a highly irregular graph is a graph in which, for every vertex, all neighbors of that vertex have distinct degrees.

History

Irregular graphs were initially characterized by Yousef Alavi, Gary Chartrand, Fan Chung, Paul Erdős, Ronald Graham, and Ortrud Oellermann. They were motivated to define the ‘opposite’ of a regular graph, a concept which has been thoroughly studied and well understood.

Locality and regularity

Defining an ‘irregular graph’ was not immediately obvious. In a k-regular graph, all vertices have degree k. In any graph G with more than one vertex, two vertices in G must have the same degree, so an irregular graph cannot be defined as a graph with all vertices of different degrees. One may be tempted then to define an irregular graph as having all vertices of distinct degrees except for two, but these types of graphs are also well understood and thus not interesting.

Graph theorists thus turned to the issue of local regularity. A graph is locally regular at a vertex v if all vertices adjacent to v have degree r. A graph is thus locally irregular if for each vertex v of G the neighbors of v have distinct degrees, and these graphs are thus termed highly irregular graphs.

Properties of irregular graphs

Some facts about highly irregular graphs outlined by Alavi et al.:

• If v is a vertex of maximum degree d in a highly irregular graph H, then v is adjacent to exactly one vertex of degree 1, 2, ..., d.
• The largest degree in a highly irregular graph is at most half the number of vertices.
• If H is a highly irregular graph with maximum degree d, one can construct a highly irregular graph of degree d+1 by taking two copies of H and adding an edge between the two vertices of degree d.
• H(n)/G(n) goes to 0 as n goes to infinity exponentially rapidly, where H(n) is the number of (non-isomorphic) highly irregular graphs with n vertices, and G(n) is the total number of graphs with n vertices.
• For every graph G, there exists a highly irregular graph H containing G as an induced subgraph.

This last observation can be considered analogous to a result of Dénes Kőnig, which states that if H is a graph with greatest degree r, then there is a graph G which is r-regular and contains H as an induced subgraph.

Applications of irregularity

Definitions of irregularity have been important in the study of network heterogeneity, which has implications in networks found across biology, ecology, technology, and economy. There have been several graph statistics that have been suggested, many of which are based on the number of vertices in a graph and their degrees. The characterization of highly irregular graphs has also been applied to the question of heterogeneity, yet all of these fail to shed enough light on real-world situations. Efforts continue to be made to find appropriate ways to quantify network heterogeneity.