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. 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 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)|}$

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

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

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