Packing of graphic n-tuples

• Published in: Journal of graph theory 2012-05, Vol.70 (1), p.29-39
• Main Authors: Busch, Arthur H., Ferrara, Michael J., Hartke, Stephen G., Jacobson, Michael S., Kaul, Hemanshu, West, Douglas B.
• Format: Article
• Language: English
• Subjects: 1-factor; degree sequence; graph packing; graphic sequence; k-factor
• ISSN: 0364-9024; 1097-0118
• DOI: 10.1002/jgt.20598

An n‐tuple π (not necessarily monotone) is graphic if there is a simple graph G with vertex set {v1, …, vn} in which the degree of vi is the ith entry of π. Graphic n‐tuples (d (1)1, …, d (1)n) and (d (2)1, …, d (2)n) pack if there are edge‐disjoint n‐vertex graphs G1 and G2 such that d G 1(vi) = d (1)i and d G 2(vi) = d (2)i for all i. We prove that graphic n‐tuples π1 and π2 pack if , where Δand δdenote the largest and smallest entries in π1 + π2 (strict inequality when δ = 1); also, the bound is sharp. Kundu and Lovász independently proved that a graphic n‐tuple π is realized by a graph with a k‐factor if the n‐tuple obtained by subtracting k from each entry of π is graphic; for even n we conjecture that in fact some realization has k edge‐disjoint 1‐factors. We prove the conjecture in the case where the largest entry of π is at most n/2 + 1 and also when k⩽3. © 2011 Wiley Periodicals, Inc. J Graph Theory