Name
Abstract | ||
|---|---|---|
Let TT"n be a transitive tournament on n vertices. It is known Gorlich, Pilsniak, Wozniak, (2006) [3] that for any acyclic oriented graph [email protected]? of order n and size not greater than 34(n-1), two graphs isomorphic to [email protected]? 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 [email protected]? of size at most 23(n-1) is embeddable into all its complements in TT"n. Moreover, this bound is generally the best possible. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.disc.2009.08.017 | Discrete Mathematics |
Keywords | Field | DocType |
transitive tournament,packing of digraphs,embedding of digraphs,graph isomorphism | Embedding problem,Discrete mathematics,Combinatorics,Tournament,Transitive reduction,Embedding,Vertex (geometry),Isomorphism,Transitive closure,Mathematics,Transitive relation | Journal |
Volume | Issue | ISSN |
310 | 4 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Agnieszka Görlich | 1 | 27 | 9.19 |
| Monika Pilśniak | 2 | 28 | 9.31 |