Originator: Garth Isaak (presented by Stephen Hartke - REGS 2008)
Definitions: A list of numbers is graphic if it is the degree list of some graph (no loops or multiple edges). A k-factor of a graph G is a spanning subgraph of G that is regular of degree k.
Background: Landau's Theorem [L] states that an n-tuple d is realizable as the outdegrees ("score sequence") of a tournament if and only if when written in nondecreasing order, the first k terms sum to at least (2k), with equality when k=n.
Question 1: Which lists of degree pairs (indegree/outdegree) are realizable as the degree pairs in a digraph without loops.
Comments: When compared to Landau's Theorem, the freedom of the indegree and outdegree to sum to less than n-1 corresponds to allowing "ties" in the tournament. When loops are allow, the problem reduces to the Gale-Ryser Theorem characterizing degree lists of bipartite graphs (separate lists for the two partite sets).
Background: Kundu's Theorem [K] states that if a list d is graphic and the list d' obtained by subtracting k from each element of d is graphic, then d is the degree list of some graph that has a k-factor.
Question 2: Can Kundu's Theorem be strengthened so that, under the same hypotheses, d has a realization containing k edge-disjoint 1-factors?
Comments: Busch, Ferrara, and Jacobson [BFJ] showed that the answer is yes when k=3. One can consider a more general situation.
Question 3: Let d¹,…,dr be graphic lists such that the list d obtained by summing them after applying a permutation to each dj is graphic. Under what conditions does there exist a graph with degree list d that decomposes into graphs with degree lists d¹,…,dr?
Comments: In the case r=2, perhaps something is known about increasing vs decreasing being easiest. There is also something about the square root of twice the length.
References:
[K] Kundu's Theorem
[L] Landau's Theorem