Download PDF - A note on careful packing of a graphAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

A note on careful packing of a graph

Authors 1

Affiliations

  1. Instytut Matematyki AGH

Abstract

Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an edge-disjoint placement of two copies of G into Kₙ. We prove that with the same condition on size of G we have actually (with few exceptions) a careful packing of G, that is an edge-disjoint placement of two copies of G into Kₙ∖Cₙ.

Keywords

ENG
pucking of graphs

Bibliography

  1. B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).
  2. B. Bollobás and S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin Theory (B) 25 (1978) 105-124, doi: 10.1016/0095-8956(78)90030-8.
  3. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, (North-Holland, New York, 1976).
  4. D. Burns and S. Schuster, Every (p,p-2)- graph is contained in its complement, J. Graph Theory 1 (1977) 277-279, doi: 10.1002/jgt.3190010308.
  5. D. Burns and S. Schuster, Embedding (n,n-1)- graphs in their complements, Israel J. Math. 30 (1978) 313-320, doi: 10.1007/BF02761996.
  6. B. Ganter, J. Pelikan and L. Teirlinck, Small sprawling systems of equicardinal sets, Ars Combinatoria 4 (1977) 133-142.
  7. N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin Theory (B) 25 (1978) 295-302, doi: 10.1016/0095-8956(78)90005-9.
  8. M. Woźniak, Embedding of graphs in the complements of their squares, in: J. Nesset ril and M. Fiedler, eds, Fourth Czechoslovakian Symp. on Combinatorics, Graphs and Complexity, (Elsevier Science Publishers B.V.,1992) 345-349.
  9. M. Woźniak, Embedding graphs of small size, Discrete Applied Math. 51 (1994) 233-241, doi: 10.1016/0166-218X(94)90112-0.
  10. M. Woźniak and A.P. Wojda, Triple placement of graphs, Graphs and Combinatorics 9 (1993) 85-91, doi: 10.1007/BF01195330.
  11. H.P. Yap, Some Topics In Graph Theory (London Mathematical Society, Lectures Notes Series 108, Cambridge University Press, Cambridge 1986).
  12. H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4.
Discussiones Mathematicae Graph Theory
1995/15/1
Export to PBN, Opens in new tab
Pages:
43-50
Main language of publication
English
Received
1994-04-26
Accepted
1994-07-14
Published
1995
Exact and natural sciences