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.^[1]

Unsolved problem in mathematics

Conjecture: If for all edges ${\displaystyle e\in E(G)}$ we have ${\displaystyle {\text{imb}}(e)>0}$, then ${\displaystyle M_{G}}$ is graphic.

More unsolved problems in mathematics

Definitions

For a simple undirected graph ${\displaystyle G}$, the imbalance of an edge ${\displaystyle e=uv}$ is defined as:

${\displaystyle {\text{imb}}(e)=|\deg(u)-\deg(v)|}$

where ${\displaystyle \deg(u)}$ and ${\displaystyle \deg(v)}$ denote the degrees of vertices ${\displaystyle u}$ and ${\displaystyle v}$ respectively.

The imbalance sequence ${\displaystyle M_{G}}$ is the multiset of all edge imbalances in ${\displaystyle 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 ${\displaystyle G}$ is called imbalance graphic if its imbalance sequence ${\displaystyle M_{G}}$ is graphic.^[2]

Statement of the conjecture

Imbalance Conjecture: If for all edges ${\displaystyle e\in E(G)}$ we have ${\displaystyle {\text{imb}}(e)>0}$, then ${\displaystyle M_{G}}$ 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.^[3] The irregularity of a graph ${\displaystyle G}$ is defined as:

${\displaystyle I(G)=\sum _{uv\in E(G)}|\deg(u)-\deg(v)|}$

This is sometimes called the Albertson index and denoted as ${\displaystyle \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.

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.^[1] This was further improved to graphs with at most 12 vertices.^[2]

Several classes of graphs have been proven to have graphic imbalance sequences. The following classes were proven imbalance graphic by Kozerenko and Skochko:^[1]

• All trees
• Graphs in which all non-leaf vertices form a clique (cl-graphs)
• Complete extensions of paths
• Complete extensions of cycles
• Complete extensions of complete graphs
• Graphs with constant edge imbalance

Kozerenko and Serdiuk established additional classes of imbalance graphic graphs:^[2]

• All unicyclic graphs (graphs with exactly one cycle)
• Antiregular graphs (graphs with exactly one pair of vertices having the same degree)
• Joins of graphs with sufficiently large empty graphs
• Double graphs of imbalance graphic 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 graphs (graphs in which the imbalance of every edge is 1) are also known to 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:^[2]

• If ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$ are imbalance graphic, then their disjoint union is also imbalance graphic
• If ${\displaystyle G}$ is imbalance graphic, then ${\displaystyle G+K_{1}}$ (the join with a single vertex) is also imbalance graphic
• The double graph of an imbalance graphic graph is also imbalance graphic

The problem would be trivial if ${\displaystyle M_{G}}$ was allowed to be the degree sequence for a multigraph, 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 multigraph.

Related conjectures

One related conjecture concerns the mean imbalance of a nonempty graph ${\displaystyle G}$, defined as:

${\displaystyle m(G)={\frac {I(G)}{|E(G)|}}}$

Mean Imbalance Conjecture: If ${\displaystyle m(G)\geq 2}$, then ${\displaystyle M_{G}}$ is graphic.^[1]

This conjecture was disproved by Kozerenko and Serdiuk in 2023, who showed that for every real number ${\displaystyle c>0}$, there exists an imbalance non-graphic graph ${\displaystyle G}$ with ${\displaystyle I(G)\geq c\cdot |E(G)|}$.^[2]

Bicyclic Graph Conjecture: There is exactly one connected imbalance non-graphic bicyclic graph (shown to exist among graphs with at most 21 vertices).^[2]

Block Graph Conjecture: All block graphs are imbalance graphic.^[2]

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.

See also

• Degree sequence
• Erdős–Gallai theorem