A note on an embedding problem in transitive tournaments

作者：Gorlich Agnieszka; Pilsniak Monika^*

来源：Discrete Mathematics, 2010, 310(4): 681-686.

DOI：10.1016/j.disc.2009.08.017

• Embedding of digraphs
• Packing of digraphs
• Transitive tournament

Let TT(n) be a transitive tournament on n vertices. It is known Gorlich, Pilsniak, Wozniak, (2006) [3] that for any acyclic oriented graph (G) over right arrow of order n and size not greater than 3/4(n - 1), two graphs isomorphic to (G) over right arrow are arc-disjoint subgraphs of TT(n). In this paper, we consider the problem of embedding of acyclic oriented graphs into their complements in transitive tournaments. We show that any acyclic oriented graph (G) over right arrow of size at most 2/3(n - 1) is embeddable into all its complements in TT(n). Moreover, this bound is generally the best possible.

• 出版日期2010-2-28