Have you come across this kind of "degree" concept?

2012-10-08T12:04:36Z

Let $A \subseteq V(G)$ be a set of vertices in a graph $G$ and let $v \in V(G)$ be some vertex. Define $d_{A}(v)$ as the number of neighbours of $v$ inside $A$.

Now suppose you have a graph whose vertex set is partitioned into $A,B,U$ and define for every vertex $u \in U$ the "AB-degree" of $u$ as $\Delta_{u}=d_{A}(u)-d_{B}(u)$.

My interest is in the special case when each vertex in $A \cup B$ has exactly $d$ neighbours in $U$. Obviously then $\sum_{u \in U}{\Delta_{u}}=d(|A|-|B|)$.

But what about $\sum_{u \in U}{|\Delta_{u}|}$? I want to find a nice upper bound for it in terms of $|A|,|B|$ and $d$ (and perhaps $|U|$, although I don't see how it can help).

I have a kind of hand-waiving argument that says it can't be too big, but I hope that somebody has already treated this kind of problem before in some detail before. Or maybe it's simple and I'm missing something?

Answer by Ben Barber for Have you come across this kind of "degree" concept?

2012-10-08T12:32:18Z

This should perhaps be a comment, but I don't have enough reputation.

What sort of bound are you hoping for? The trivial bound $d(|A|+|B|)$ appears to be tight: take $G=K_{d,d}$ with $A$ one of the parts and $B$ empty. (Two copies of this will give you an example with $A$ and $B$ the same size.)

Have you come across this kind of "degree" concept? - MathOverflow

Have you come across this kind of "degree" concept?

Answer by Ben Barber for Have you come across this kind of "degree" concept?