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
    Commented 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
    Commented Oct 8, 2012 at 12:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .