Sali, Attila and Simonyi, Gábor and Tardos, Gábor (2020) Partitioning Transitive Tournaments into Isomorphic Digraphs. ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS. pp. 1-17. ISSN 0167-8094 (print); 1572-9273 (online)
|
Text
1806.pdf Available under License Creative Commons Attribution. Download (353kB) | Preview |
Abstract
In an earlier paper (see Sali and Simonyi Eur. J. Combin. 20, 93–99, 1999) the first two authors have shown that self-complementary graphs can always be oriented in such a way that the union of the oriented version and its isomorphically oriented complement gives a transitive tournament. We investigate the possibilities of generalizing this theorem to decompositions of the complete graph into three or more isomorphic graphs. We find that a complete characterization of when an orientation with similar properties is possible seems elusive. Nevertheless, we give sufficient conditions that generalize the earlier theorem and also imply that decompositions of odd vertex complete graphs to Hamiltonian cycles admit such an orientation. These conditions are further generalized and some necessary conditions are given as well. © 2020, The Author(s).
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | graph orientation; decomposition to isomorphic graphs; transitive tournament |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 18 Aug 2020 07:15 |
| Last Modified: | 21 Apr 2023 09:49 |
| URI: | http://real.mtak.hu/id/eprint/112244 |
Actions (login required)
 |
Edit Item |
