Packing of three copies of a digraph into the transitive tournament

Monika Pilśniak

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 3, page 443-456
  • ISSN: 2083-5892

Abstract

top
In this paper, we show that if the number of arcs in an oriented graph G (of order n) without directed cycles is sufficiently small (not greater than [2/3] n-1), then there exist arc disjoint embeddings of three copies of G into the transitive tournament TTₙ. It is the best possible bound.

How to cite

top

Monika Pilśniak. "Packing of three copies of a digraph into the transitive tournament." Discussiones Mathematicae Graph Theory 24.3 (2004): 443-456. <http://eudml.org/doc/270549>.

@article{MonikaPilśniak2004,
abstract = {In this paper, we show that if the number of arcs in an oriented graph G (of order n) without directed cycles is sufficiently small (not greater than [2/3] n-1), then there exist arc disjoint embeddings of three copies of G into the transitive tournament TTₙ. It is the best possible bound.},
author = {Monika Pilśniak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {packing of digraphs; transitive tournament},
language = {eng},
number = {3},
pages = {443-456},
title = {Packing of three copies of a digraph into the transitive tournament},
url = {http://eudml.org/doc/270549},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Monika Pilśniak
TI - Packing of three copies of a digraph into the transitive tournament
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 443
EP - 456
AB - In this paper, we show that if the number of arcs in an oriented graph G (of order n) without directed cycles is sufficiently small (not greater than [2/3] n-1), then there exist arc disjoint embeddings of three copies of G into the transitive tournament TTₙ. It is the best possible bound.
LA - eng
KW - packing of digraphs; transitive tournament
UR - http://eudml.org/doc/270549
ER -

References

top
  1. [1] B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978). 
  2. [2] B. Bollobás and S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory 25 (B) (1978) 105-124. Zbl0387.05020
  3. [3] D. Burns and S. Schuster, Every (n,n-2) graph is contained in its complement, J. Graph Theory 1 (1977) 277-279, doi: 10.1002/jgt.3190010308. Zbl0375.05046
  4. [4] A. Görlich, M. Pilśniak and M. Woźniak, A note on a packing problem in transitive tournaments, preprint Faculty of Applied Mathematics, University of Mining and Metallurgy, No.37/2002. Zbl1100.05074
  5. [5] H. Kheddouci, S. Marshall, J.F. Saclé and M. Woźniak, On the packing of three graphs, Discrete Math. 236 (2001) 197-225, doi: 10.1016/S0012-365X(00)00443-X. Zbl0998.05053
  6. [6] N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory 25 (B) (1978) 295-302. Zbl0417.05037
  7. [7] M. Woźniak and A.P. Wojda, Triple placement of graphs, Graphs and Combin. 9 (1993) 85-91, doi: 10.1007/BF01195330. Zbl0817.05034
  8. [8] M. Woźniak, Packing of graphs, Dissertationes Math. 362 (1997). 
  9. [9] H.P. Yap, Some Topics in Graph Theory, London Math. Society, Lectures Notes Series, Vol. 108 (Cambridge University Press, Cambridge, 1986). Zbl0588.05002
  10. [10] H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4. Zbl0685.05036

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.