Embeddings of graphs into their complements in transi- tive tournaments
Agnieszka Görlich · 2006
In [1] the authors have proved a basic result concerning a packing of a simple graph G of order n into the complete graph Kn: if |E(G)| 6 n - 2, then there exists such a packing. A packing of a simple graph G in Kn means exactly the same as an embedding of a graph G into its complement in Kn. Let − − → TTn be a transitive tournament on n vertices. Packing and embedding problems in − − → TTn are not equivalent. It is known [2] that for any directed acyclic graph − G of order n and of size not greater than 3 4 (n - 1) two directed graphs isomorphic to − G are arc disjoint subgraphs of − − → TTn. We consider a problem of an embedding of a graph − G into its complement in − − → TTn. We show that any directed acyclic graph − G of size not greater than 2 (n - 1) is embeddable into its complement in − − → TTn. Moreover, this bound is generally the best possible.