1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ok, you are right, of course - but I have in mind a situation where $A,B$ are non-empty and somewhat smaller than $U$ - in that case the trivial bound is excessively large. My feeling is that the true value can be bounded by something like $2.5d(|A|-|B|)$. $\endgroup$
    – Felix Goldberg
    Oct 8, 2012 at 12:37
  • $\begingroup$ It looks like you'll still need some more structure. Taking any example, we can obtain an example with $|A|=|B|$ by taking two disjoint copies, and then the hoped for bound will vanish. The "$U$ large" condition doesn't seem very useful, as we only care about the at most $d(|A|+|B|)$ vertices adjacent to $A \cup B$. For $\sum_{u \in U} \Delta_u$ to be smaller than $d(|A|+|B|)$ you need to know something about how many $u \in U$ have neighbours in both $A$ and $B$. $\endgroup$
    – Ben Barber
    Oct 8, 2012 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.