Let G(1), and G(2) be graphs of order n with maximum degree Delta(1), and Delta(2), respectively. G(1) and G(2) are said to pack if there exist injective mappings of the vertex sets into [n], such that the images of the edge sets do not intersect. Sauer and Spencer showed that if Delta(1)Delta(2) < (n)/(2), then G(1), and G(2) pack. We extend this result by showing that if Delta(1)Delta(2) <= (n)/(2), then G(1) and G(2) do not pack if and only if one of G(1) or G(2) is a perfect matching and the other either is K-n/2,K-n/2 with (n)/(2) odd or contains Kn/2+1.
展开▼
