0
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.