7
$\begingroup$

Let $G$ be simple undirected graph and $e=uv\in E(G)$.

The imbalance of the edge $e$ is the value $imb(e)=|d(u)-d(v)|$.

Let $M_{G}$ denotes the imbalance sequence (or more correctly, multiset of all edge imbalances) of $G$.

I can prove that if $T$ is a tree, then $M_{T}$ is graphic.

However, in general case it isn't true. See A question on graphic sequences for simple counterexamples.

Based on these I came to the next

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

ADDED 1: Vova Skochko, a good friend of mine, verified the conjecture for all such graphs with $\leq 9$ vertices.

ADDED 2: Recall that the value $Irr(G)=\sum_{e\in E(G)}imb(e)$ is called irregularity of $G$.

In light of Erdos-Gallai theorem the Imbalance Conjecture is equivalent to the next statement

Suppose that for all edges $e\in E(G)$ we have $imb(e)>0$. Then for all $E'\subset E(G)$ it holds $$Irr(G)\leq |E'|(|E'|-1)+\sum_{e\notin E'}\left(\min\{{|E'|,imb(e)}\}+imb(e)\right).$$

I wonder does this bound on $Irr(G)$ implies other known bounds on $Irr(G)$ for such graphs?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Sergiy, It seems like for any graph, the imbalance sequence is the degree sequence of a multigraph (repeated edges allowed). For trees this multigraph happens to be a simple graph. Perhaps the question should be to find a direct description of the associated multigraph from the original graph. $\endgroup$ – Gjergji Zaimi Sep 1 '13 at 22:10
  • 1
    $\begingroup$ Gjergji Zaimi, I'm interested in degrees sequences of simple graphs, not multigraphs. However, it is easy to see that $\sum M_{G}$ is always even, so the imbalance sequence of any graph is the degree sequence of some pseudograph. Oh, and I'm curious how can you prove that the imbalance sequence of a tree is graphic? Because my proof is inductional. $\endgroup$ – Sergiy Kozerenko Sep 2 '13 at 11:18
  • 1
    $\begingroup$ Jernej, no it's not! For counterexample on $9$ vertices see mathoverflow.net/questions/140198/… $\endgroup$ – Sergiy Kozerenko Sep 3 '13 at 12:00
  • 2
    $\begingroup$ Obviously, I like this question :) Is there some special motivation or just curiosity? $\endgroup$ – Felix Goldberg Sep 8 '13 at 14:19
  • 1
    $\begingroup$ @Gjergji Zaimi: It is known that the multiset $M$ is multigraphic if and only if $\sum M$ is even and $\sum M\geq 2\max M$. Thus for every even $m\in\mathbb{N}$ one can take any $m+1$-regular graph $H$ with $\geq 4$ vertices, such that $H$ has a matching of a size $\frac{m}{2}$ (for example $H=K_{m+1,m+1}$). Then delete this matching, add new vertex $v$ and new edges from $v$ to the vertices from this matching. Then again add a new vertex $u$ and the edge $uv$ to obtain a new graph $G$. We have, that $M_{G}=\{m\}$ is not multigraphic. $\endgroup$ – Sergiy Kozerenko Sep 11 '13 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.