TY - JOUR
T1 - Extremal graphs for a graph packing theorem of Sauer and Spencer
AU - Kaul, Hemanshu
AU - Kostochka, Alexandr
N1 - Funding Information:
† Research of this author was partially supported by the NSF grant DMS-0400498 and grant 03-01-00796 of the Russian Foundation for Basic Research.
PY - 2007/5
Y1 - 2007/5
N2 - Let G1 and G2 be graphs of order n with maximum degree Δ1 and Δ2, respectively. G1 and G2 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 Δ1Δ2 < n/2, then G1 and G2 pack. We extend this result by showing that if, then GΔ1 and Δ2 do not pack if and only if one of G1 or G2 is a perfect matching and the other either is Kn/2,n/2 with n/2 odd or contains Kn/2+1.
AB - Let G1 and G2 be graphs of order n with maximum degree Δ1 and Δ2, respectively. G1 and G2 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 Δ1Δ2 < n/2, then G1 and G2 pack. We extend this result by showing that if, then GΔ1 and Δ2 do not pack if and only if one of G1 or G2 is a perfect matching and the other either is Kn/2,n/2 with n/2 odd or contains Kn/2+1.
UR - http://www.scopus.com/inward/record.url?scp=34247636585&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34247636585&partnerID=8YFLogxK
U2 - 10.1017/S0963548306007929
DO - 10.1017/S0963548306007929
M3 - Article
AN - SCOPUS:34247636585
SN - 0963-5483
VL - 16
SP - 409
EP - 416
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
IS - 3
ER -