Packing of graphic n ‐tuples
Arthur H. Busch, Michael J. Ferrara, Stephen G. Hartke, Michael S. Jacobson, Hemanshu Kaul, Douglas B. West · Journal of Graph Theory · 2011
Abstract An n ‐tuple π (not necessarily monotone) is graphic if there is a simple graph G with vertex set { v 1 , …, v n } in which the degree of v i is the i th entry of π. Graphic n ‐tuples ( d , …, d ) and ( d , …, d ) pack if there are edge‐disjoint n ‐vertex graphs G 1 and G 2 such that d ( v i ) = d and d ( v i ) = d 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