Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-10T07:21:38.210Z Has data issue: false hasContentIssue false
  • English
  • Français

Extremal Graphs for a Graph Packing Theorem of Sauer and Spencer

Published online by Cambridge University Press:  01 May 2007

HEMANSHU KAUL  and
ALEXANDR KOSTOCHKA
HEMANSHU KAUL
Affiliation:
Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA (e-mail: hkaul@math.uiuc.edu, kostochk@math.uiuc.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 $\Delta_1 \Delta_2<\frac{n}{2}$, then G1 and G2 pack. We extend this result by showing that if $\Delta_1 \Delta_2 \leq \frac{n}{2}$, then G1 and G2 do not pack if and only if one of G1 or G2 is a perfect matching and the other either is $K_{\frac{n}{2},\frac{n}{2}}$ with $\frac{n}{2}$ odd or contains $K_{\frac{n}{2} + 1}$.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 3 , May 2007 , pp. 409 - 416
Copyright
Copyright © Cambridge University Press 2006

References

[1]Bollobás, B. (1978) Extremal Graph Theory, Academic Press, London/New York.Google Scholar
[2]Bollobás, B. and Eldridge, S. E. (1978) Packing of graphs and applications to computational complexity. J. Combin. Theory Ser. B 25 105–124.CrossRefGoogle Scholar
[3]Catlin, P. A. (1974) Subgraphs of graphs I. Discrete Math. 10 225–233.CrossRefGoogle Scholar
[4]Sauer, N. and Spencer, J. (1978) Edge disjoint placement of graphs. J. Combin. Theory Ser. B 25 295–302.CrossRefGoogle Scholar
[5]Wozniak, M. (1997) Packing of graphs. Dissertationes Math. 362 78pp.Google Scholar
[6]Yap, H. P. (1988) Packing of graphs: A survey. Discrete Math. 72 395–404.CrossRefGoogle Scholar