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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.