Highly irregular graph

with unique degrees.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

with unique degrees. For example, the black vertex has the yellow vertices as its neighbors, which have degrees 1, 2 and 3. 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 each 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 is 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.

See also

Stepwise irregular graph Imbalance conjecture

Text derived from https://en.wikipedia.org/w/index.php?oldid=1366383811 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001366383811 · captured 1785169737.0 · version history

Cite this page as: encyclopegia.org, “Highly irregular graph”, snapshot enwiki-001366383811. https://encyclopegia.org/a/highly-irregular-graph

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.