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

Christian Germain; Hamamache Kheddouci

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 1, page 105-115
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Christian Germain, and Hamamache Kheddouci. "On the packing of two copies of a caterpillar in its third power." Discussiones Mathematicae Graph Theory 23.1 (2003): 105-115. <http://eudml.org/doc/270752>.

@article{ChristianGermain2003,
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.},
author = {Christian Germain, Hamamache Kheddouci},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {packing; placement; permutation; power of tree; caterpillar},
language = {eng},
number = {1},
pages = {105-115},
title = {On the packing of two copies of a caterpillar in its third power},
url = {http://eudml.org/doc/270752},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Christian Germain
AU - Hamamache Kheddouci
TI - On the packing of two copies of a caterpillar in its third power
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 1
SP - 105
EP - 115
AB - 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.
LA - eng
KW - packing; placement; permutation; power of tree; caterpillar
UR - http://eudml.org/doc/270752
ER -

References

top
  1. [1] B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978). 
  2. [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. Zbl0843.05026
  3. [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. Zbl0375.05046
  4. [4] S.M. Hedetniemi, S.T. Hedetniemi and P.J. Slater, A note on packing two trees into K N , Ars Combin. 11 (1981) 149-153. Zbl0491.05050
  5. [5] H. Kheddouci, Packing of some trees into their third power, to appear in Appl. Math. Letters. Zbl1039.05048
  6. [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. Zbl0956.05080
  7. [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. Zbl0417.05037
  8. [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. Zbl0773.05084
  9. [9] M. Woźniak, A note on embedding graphs without small cycles, Colloq. Math. Soc. J. Bolyai 60 (1991) 727-732. 
  10. [10] M. Woźniak, Packing of Graphs, Dissertationes Math. CCCLXII (1997) pp. 78. 
  11. [11] H.P. Yap, Some Topics in Graph Theory, London Mathematical Society, Lectures Notes Series 108 (Cambridge University Press, Cambridge, 1986). Zbl0588.05002

NotesEmbed ?

top

You must be logged in to post comments.