Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-02T20:21:46.278Z 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: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 , then G1 and G2 pack. We extend this result by showing that if , 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 with odd or contains .

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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