Packing of graphic n‐tuples |
| |
| Authors: | Arthur H. Busch Michael J. Ferrara Stephen G. Hartke Michael S. Jacobson Hemanshu Kaul Douglas B. West |
| |
| Affiliation: | 1. University of dayton, , Dayton, Ohio;2. University of colorado denver, , Denver, Colorado;3. University of nebraska‐lincoln;4. Illinois institute of technology chicago, , Illinois;5. University of illinois, , Urbana, Illinois |
| |
| Abstract: | 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 , …, d ) and (d , …, d ) pack if there are edge‐disjoint n‐vertex graphs G1 and G2 such that d (vi) = d and d (vi) = 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 |
| |
| Keywords: | degree sequence graphic sequence graph packing k‐factor 1‐factor |
|
|
