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 G {\displaystyle G} , the imbalance of an edge e = u v {\displaystyle e=uv} is defined as:
imb ( e ) = | deg ( u ) − deg ( v ) | {\displaystyle {\text{imb}}(e)=|\deg(u)-\deg(v)|}
where deg ( u ) {\displaystyle \deg(u)} and deg ( v ) {\displaystyle \deg(v)} denote the degrees of vertices u {\displaystyle u} and v {\displaystyle v} respectively. The imbalance sequence M G {\displaystyle M_{G}} is the multiset of all edge imbalances in G {\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 G {\displaystyle G} is called imbalance graphic if its imbalance sequence M G {\displaystyle M_{G}} is graphic.
Statement of the conjecture Imbalance Conjecture: If for all edges e ∈ E ( G ) {\displaystyle e\in E(G)} we have imb ( e ) > 0 {\displaystyle {\text{imb}}(e)>0} , then M G {\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. The irregularity of a graph G {\displaystyle G} is defined as:
I ( G ) = ∑ u v ∈ E ( G ) | deg ( u ) − deg ( v ) | {\displaystyle I(G)=\sum _{uv\in E(G)}|\deg(u)-\deg(v)|}
This is sometimes called the Albertson index and denoted as Alb ( G ) {\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. 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:
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:
All unicyclic graphs (graphs with exactly one cycle) Antiregular graphs (graphs with exactly one pair of vertices having the same degree) 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 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 G 1 {\displaystyle G_{1}} and G 2 {\displaystyle G_{2}} are imbalance graphic, then their disjoint union is also imbalance graphic The join of graphs with sufficiently large empty graphs is imbalance graphic If G {\displaystyle G} is imbalance graphic, then so is G + K 1 {\displaystyle G+K_{1}} (the join with a single vertex) The double graph of an imbalance graphic graph is also imbalance graphic The problem would be trivial if M G {\displaystyle M_{G}} 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 G {\displaystyle G} , defined as:
… excerpt ends here. Continue reading the full article.
