Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w_i$ denote the (integer) weight of graph $G$, with $\sum_i w_i = m$ the total weight in the graph. The average weight per node then is $\bar w = m/n$. Let $e_i = w_i - \bar w$ denote the deviation of node $i$ from the mean. We call $|e_i|$ the imbalance of node $i$.
Suppose that the weight between any two adjacent nodes can differ by at most $1$, i.e., $$ w_i - w_j \le 1\; \forall (i,j) \in E.$$
Question: What is the largest possible imbalance the network can have, in terms of $n$ and $m$? To be more precise, picture the vector $\vec{e} = (e_1, \dots, e_n)$. I'd be equally content with results concerning $||\vec{e}||_1$ or $||\vec{e}||_2$.
For $||\vec{e}||_\infty$, a simple bound in terms of the graph diameter can be found: Since all $e_i$ must sum to zero, if there is a large positive $e_i$, there must somewhere be a negative $e_j$. Hence their difference $|e_i - e_j|$ is at least $|e_i|$, but this difference can be at most the shortest distance between nodes $i$ and $j$, which in turn can be at most the graph diameter.
I'm interested in stronger bounds, preferably for the $1$- or $2$-norm. I suppose it should involve some spectral graph theory to reflect the connectivity of the graph. I tried expressing it as a max-flow problem, to no avail.
EDIT: More explanation. I'm interested in the $1$- or $2$-norm as they more accurately reflect the total imbalance. A trivial relation would be obtained from $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$, and $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$. I expect, however, that due to the connectedness of the graph and my constraint in the difference of loads between adjacent nodes, that the $1$- and $2$-norms should be much smaller.
Example: Hypercube of Dimension d, with $n = 2^d$. It has diameter $d = \log_2(n)$. The maximum imbalance is then at most $d$. This suggest as an upper bound for the $1$-norm $nd = n\log_2(n)$. So far, I have been unable to construct a situation where this is actually obtained, the best I can do is something along the lines of $||\vec{e}||_1 = n/2$, where I embed a cycle into the Hypercube and have the nodes have imbalances $0$, $1$, $0$, $-1$ etc. So, here the bound is off by a factor of $\log(n)$, which I consider already too much, as I'm looking for (asymptotically) tight bounds.