Imbalance conjecture

Importance: Medium ✭✭

Author(s):

Subject:

Keywords:	edge imbalance
	graphic sequences

Recomm. for undergrads: no

Posted	by:	Sergiy Kozerenko
	on:	September 24th, 2013

Conjecture Suppose that for all edges $e\in E(G)$ we have $imb(e)>0$ . Then $M_{G}$ is graphic.

Consider simple undirected graph $G$ and let $e=uv\in E(G)$ .

The imbalance of the edge $e$ defined as $imb(e)=|deg(u)-deg(v)|$ .

The multiset of all edge imbalances of $G$ is denoted by $M_{G}$ .

Note, that conjecture is verified for all such graphs with $\leq 9$ vertices.

Bibliography

* indicates original appearance(s) of problem.