DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 23(1) (2003) 105-115
DOI: 10.7151/dmgt.1188

ON THE PACKING OF TWO COPIES OF A CATERPILLAR IN ITS THIRD POWER

Christian Germain and Hamamache Kheddouci

LE2I, FRE-CNRS 2309, Université de Bourgogne
B.P. 47870, 21078 Dijon Cedex, France
e-mail: CGermain@u-bourgogne.fr, KHeddouc@u-bourgogne.fr

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: packing, placement, permutation, power of tree, cater- pillar.

2000 Mathematics Subject Classification: 05C70 (05C05).

References

[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). 

Received 10 July 2001
Revised 5 July 2002