Download PDF - On the packing of two copies of a caterpillar in its third powerAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On the packing of two copies of a caterpillar in its third power

Authors 1, 1

Affiliations

  1. LE2I, FRE-CNRS 2309, Université de Bourgogne, B.P. 47870, 21078 Dijon Cedex, France

Abstract

H. Kheddouci, J.F. Saclé and M. Woźniak conjectured in 2000 that if a tree T is not a star, then there is an edge-disjoint placement of T into its third power.In this paper, we prove the conjecture for caterpillars.

Keywords

ENG
packing, placement, permutation, power of tree, caterpillar

Bibliography

  1. B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).
  2. S. Brandt, Embedding graphs without short cycles in their complements, in: Y. Alavi and A. Schwenk, eds., Graph Theory, Combinatorics, and Applications of Graphs, Vol. 1 (John Wiley and Sons, 1995), 115-121.
  3. 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.
  4. S.M. Hedetniemi, S.T. Hedetniemi and P.J. Slater, A note on packing two trees into KN, Ars Combin. 11 (1981) 149-153.
  5. H. Kheddouci, Packing of some trees into their third power, to appear in Appl. Math. Letters.
  6. H. Kheddouci, J.F. Saclé and M. Woźniak, Packing of two copies of a tree into its fourth power, Discrete Math. 213 (2000) 169-178, doi: 10.1016/S0012-365X(99)00177-6.
  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. H. Wang and N. Sauer, Packing three copies of a tree into a complete graph, Europ. J. Combin. 14 (1993) 137-142, doi: 10.1006/eujc.1993.1018.
  9. M. Woźniak, A note on embedding graphs without small cycles, Colloq. Math. Soc. J. Bolyai 60 (1991) 727-732.
  10. M. Woźniak, Packing of Graphs, Dissertationes Math. CCCLXII (1997) pp. 78.
  11. H.P. Yap, Some Topics in Graph Theory, London Mathematical Society, Lectures Notes Series 108 (Cambridge University Press, Cambridge, 1986).
Discussiones Mathematicae Graph Theory
2003/23/1
Export to PBN, Opens in new tab
Pages:
105-115
Main language of publication
English
Received
2001-07-10
Accepted
2002-07-05
Published
2003

DOI: 10.7151/dmgt.1188

Exact and natural sciences