Imbalance conjecture

, and the degree of the vertices in the blue graph are exactly the imbalance of the edge of the gray graph they lie on (the difference between the degrees of the vertices incident to it).

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 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.

, and the degree of the vertices in the blue graph are exactly the imbalance of the edge of the gray graph they lie on (the difference between the degrees of the vertices incident to it). The imbalance conjecture is an open problem in graph theory concerning whether edge imbalance sequences are graphic, first formally stated by Kozerenko and Skochko in 2014.

For a simple undirected graph G , the imbalance of an edge e = uv is defined as: \text{imb}(e) = |\deg(u) - \deg(v)| where \deg(u) and \deg(v) denote the degrees of vertices u and v respectively. The imbalance sequence M_G is the multiset of all edge imbalances in G . A sequence of non-negative integers is called graphic if it is the degree sequence of some graph.

Note that the term sometimes allows a multigraph, but here it is defined as the degree sequence of a simple graph. A graph G is called imbalance graphic if its imbalance sequence M_G is graphic. I(G) = \sum_{uv \in E(G)} |\deg(u) - \deg(v)| This is sometimes called the Albertson index and denoted as \operatorname{Alb}(G) in the literature.

While considerable research has focused on bounds for graph irregularity, Kozerenko and Skochko were the first to systematically study imbalance sequences as objects of interest in their own right. m(G) = \frac{I(G)} Mean Imbalance Conjecture: If m(G) \geq 2 , then M_G is graphic. This conjecture was disproved by Kozerenko and Serdiuk in 2023, who showed that for every real number c > 0 , there exists an imbalance non-graphic graph G with I(G) \geq c \cdot |E(G)| .

Bicyclic Graph Conjecture: There is exactly one connected imbalance non-graphic bicyclic graph (shown to exist among graphs with at most 21 vertices). Block Graph Conjecture: All block graphs are imbalance graphic. This conjecture has been verified for all block graphs with at most 13 vertices.

A weaker version conjectures that all line graphs of trees (which are exactly claw-free block graphs) are imbalance graphic.

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

Sources cited in this revision

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