Packing of three copies of a digraph into the transitive tournament

Monika Pilśniak

ArticleOriginal scientific text

Title

Packing of three copies of a digraph into the transitive tournament

Authors ¹

Affiliations

Faculty of Applied Mathematics AGH, Department of Discrete Mathematics, al. Mickiewicza 30, 30-059 Kraków, Poland

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.

Keywords

ENG

packing of digraphs, transitive tournament

B. Bollobás, Extremal Graph Theory (Academic Press, London, 1978).
B. Bollobás and S.E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory 25 (B) (1978) 105-124.
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.
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.
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.
N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory 25 (B) (1978) 295-302.
M. Woźniak and A.P. Wojda, Triple placement of graphs, Graphs and Combin. 9 (1993) 85-91, doi: 10.1007/BF01195330.
M. Woźniak, Packing of graphs, Dissertationes Math. 362 (1997).
H.P. Yap, Some Topics in Graph Theory, London Math. Society, Lectures Notes Series, Vol. 108 (Cambridge University Press, Cambridge, 1986).
H.P. Yap, Packing of graphs - a survey, Discrete Math. 72 (1988) 395-404, doi: 10.1016/0012-365X(88)90232-4.

Title

Packing of three copies of a digraph into the transitive tournament

Affiliations

Abstract

Keywords

Bibliography