10
$\begingroup$

It is known that the sequence $d_1 \geq d_2 \geq \ldots \geq d_n$ of nonnegative integers is the degree sequence of a graph if and only if the sum of the $d_i$ is even and we have \[ \sum_{i = 1}^k d_i \leq k(k - 1) + \sum_{i = k + 1}^n \min(d_i, k) \] for all $k \in \{1, \ldots, n\}$. (This is the Erdős–Gallai theorem.) There is also a simple algorithm (the Havel-Hakimi algorithm) for producing a graph with a given valid degree sequence.

Is there a simple characterization of pairs $\{(a_1 \geq \ldots \geq a_m), (b_1 \geq \ldots \geq b_n)\}$ of sequences of nonnegative integers such that there exists a bipartite graph with the property that the degrees of the vertices in one part are given by the $a_i$ and the degrees of the vertices in the other part is given by the $b_j$?

An obvious necessary condition is that $\sum a_i = \sum b_j$, but this is also clearly not sufficient. One can also ask for an algorithm analogous to Havel-Hakimi.

$\endgroup$

3 Answers 3

10
$\begingroup$

So you are looking for the Gale-Ryser theorem. There is a version of Havel-Hakimi for bipartite graphs as well. It says that the pair $(P,Q)$ is bigraphic if and only if the pair $(P',Q')$ is bigraphic, where $(P', Q')$ is obtained from $(P, Q)$ by deleting the largest element $p_1$ of $P$ and subtracting one from each of the $p_1$ largest elements of $Q$.

$\endgroup$
2
  • $\begingroup$ Do you have a reference for this version of the Havel-Hakimi construction? $\endgroup$ Mar 27, 2021 at 9:05
  • $\begingroup$ @SzabolcsHorvát See exercise 1.4.32 of Introduction to Graph Theory, by D.B. West. $\endgroup$ Mar 27, 2021 at 16:30
3
$\begingroup$

This is only a semi-answer: The existence of such a graph is equivalent to finding the maximal flow in a network where the source is connected to all the "red" vertices by edges of capacities $a_1, \dots, a_n$, the sink is connected to all the "blue" vertices by edges of capacity $b_1, \dots, b_n$ and every blue edge is connected to every red edge by an edge of capacity $1.$ If the maximal flow equals $\sum a_i = \sum b_j,$ then the degree sequence exists. Finding such a flow is quite fast (see, eg, Ahuja and Orlin's book on network flow).

$\endgroup$
2
  • 1
    $\begingroup$ Presumably the max-flow min-cut theorem can be transformed into a characterization of the valid degree sequences. $\endgroup$ Dec 9, 2010 at 3:34
  • 1
    $\begingroup$ There might be some strengthening of the Hall Marriage Theorem, but it does not jump out at me :( $\endgroup$
    – Igor Rivin
    Dec 9, 2010 at 3:39
-2
$\begingroup$

Potentially and forcibly bigraphic sequences are characterized by T. Gangopadhyay way back in eighties.

$\endgroup$
1
  • 2
    $\begingroup$ Could you give a reference? $\endgroup$ Jun 21, 2014 at 10:26

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.