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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you have a reference for this version of the Havel-Hakimi construction? $\endgroup$
    – Szabolcs Horvát
    Commented Mar 27, 2021 at 9:05
  • $\begingroup$ @SzabolcsHorvát See exercise 1.4.32 of Introduction to Graph Theory, by D.B. West. $\endgroup$
    – Gjergji Zaimi
    Commented 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).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Presumably the max-flow min-cut theorem can be transformed into a characterization of the valid degree sequences. $\endgroup$
    – David Eppstein
    Commented 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
    Commented Dec 9, 2010 at 3:39
-2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Could you give a reference? $\endgroup$
    – Dag Oskar Madsen
    Commented Jun 21, 2014 at 10:26

You must log in to answer this question.

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