Imbalance conjecture


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.

Definitions

For a simple undirected graph, the imbalance of an edge is defined as:
where and denote the degrees of vertices and respectively.
The imbalance sequence is the multiset of all edge imbalances in.
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 is called imbalance graphic if its imbalance sequence is graphic.

Statement of the conjecture

Imbalance Conjecture: If for all edges we have, then is graphic.
In other words, if no edge in a graph connects vertices of equal degree, then the multiset of edge imbalances forms a valid degree sequence for some simple graph.

Background

The concept of edge imbalance was introduced by Albertson in 1997 as a measure of graph irregularity. The irregularity of a graph is defined as:
This is sometimes called the Albertson index and denoted as 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.

Known results

The imbalance conjecture has been computationally verified for all graphs with at most 9 vertices satisfying the condition that all edges have positive imbalance. This was further improved to graphs with at most 12 vertices.
Several classes of graphs have been proven to have graphic imbalance sequences. The following classes were proven imbalance graphic by Kozerenko and Skochko:
Kozerenko and Serdiuk established additional classes of imbalance graphic graphs:
  • All unicyclic graphs
  • Antiregular graphs
  • Three special classes of block graphs:
  • *Block graphs having all cut vertices in a single block
  • *Block graphs in which cut vertices induce a star
  • *Block graphs in which cut vertices induce a path
Stepwise [irregular graph]s are also known to have graphic imbalance sequences; these are all in the form of some number of disjoint 2-paths.
Various graph operations have been shown to preserve the property of being imbalance graphic:
  • If and are imbalance graphic, then their disjoint union is also imbalance graphic
  • The join of graphs with sufficiently large empty graphs is imbalance graphic
  • If is imbalance graphic, then so is
  • The double graph of an imbalance graphic graph is also imbalance graphic
The problem would be trivial if was allowed to be the degree sequence for a pseudograph, because the Albertson index is always an even number, and any non-increasing sequence of positive integers with an even sum is the degree sequence of a pseudograph.

Related conjectures

One related conjecture concerns the mean imbalance of a nonempty graph, defined as:
Mean Imbalance Conjecture: If, then is graphic.
This conjecture was disproved by Kozerenko and Serdiuk in 2023, who showed that for every real number, there exists an imbalance non-graphic graph with.
Bicyclic Graph Conjecture: There is exactly one connected imbalance non-graphic bicyclic graph.
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 are imbalance graphic.