On the packing of two copies of a caterpillar in its third power
Christian Germain ; Hamamache Kheddouci
Discussiones Mathematicae Graph Theory, Tome 23 (2003), p. 105-115 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2003-01-01
EUDML-ID : urn:eudml:doc:270752 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1188,
     author = {Christian Germain and Hamamache Kheddouci},
     title = {On the packing of two copies of a caterpillar in its third power},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {23},
     year = {2003},
     pages = {105-115},
     zbl = {1037.05040},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1188}
}

Christian Germain; Hamamache Kheddouci. On the packing of two copies of a caterpillar in its third power. Discussiones Mathematicae Graph Theory, Tome 23 (2003) pp. 105-115. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1188/

[000] [1] B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).

[001] [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. | Zbl 0843.05026

[002] [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. | Zbl 0375.05046

[003] [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. | Zbl 0491.05050

[004] [5] H. Kheddouci, Packing of some trees into their third power, to appear in Appl. Math. Letters. | Zbl 1039.05048

[005] [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. | Zbl 0956.05080

[006] [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. | Zbl 0417.05037

[007] [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. | Zbl 0773.05084

[008] [9] M. Woźniak, A note on embedding graphs without small cycles, Colloq. Math. Soc. J. Bolyai 60 (1991) 727-732.

[009] [10] M. Woźniak, Packing of Graphs, Dissertationes Math. CCCLXII (1997) pp. 78.

[010] [11] H.P. Yap, Some Topics in Graph Theory, London Mathematical Society, Lectures Notes Series 108 (Cambridge University Press, Cambridge, 1986). | Zbl 0588.05002