In graph theory, a highly irregular graph is a graph in which, for every vertex, all neighbors of that vertex have distinct degrees.
Contents
History
Irregular graphs were initially characterized by Yousef Alavi, Gary Chartrand, Fan Chung, Paul Erdős, R L Graham, and Ortrud Oellerman. 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, 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.:
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.