Take the 2-minute tour ×

Let $G = (U, V, E)$ be a bipartite graph with $|U| = |V|$, $|U|$ large. If the median degree of a node in U is 4, and the median degree of a node in V is 7, is there a way to tell whether the degree distribution of U or V has a greater standard deviation?

share|improve this question
add comment

1 Answer

Not with this information alone. Indeed, nothing you assumed contradicts the maximal degree's being 11 or less and in that case you can just make another graph with degrees $11-d_j$ instead of $d_j$ (all you really need for the existence of the bipartite graph with given degrees is that the total degree of vertices in $U$ is the same as the total degree of vertices in $V$; this is literally true if you allow multiple edges and true under the assumption that all degrees are much less than $|U|,|V|$ if you do not). But that other graph has the medians reversed and the same standard deviations as the original one.

share|improve this answer
add comment

Your Answer


