| Title:
|
Cycles with a given number of vertices from each partite set in regular multipartite tournaments (English) |
| Author:
|
Volkmann, Lutz |
| Author:
|
Winzen, Stefan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
56 |
| Issue:
|
3 |
| Year:
|
2006 |
| Pages:
|
827-843 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
If $x$ is a vertex of a digraph $D$, then we denote by $d^+(x)$ and $d^-(x)$ the outdegree and the indegree of $x$, respectively. A digraph $D$ is called regular, if there is a number $p \in \mathbb{N}$ such that $d^+(x) = d^-(x) = p$ for all vertices $x$ of $D$. A $c$-partite tournament is an orientation of a complete $c$-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether $c$-partite tournaments with $r$ vertices in each partite set contain a cycle with exactly $r-1$ vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if $c = 2$. If $c \ge 3$, then we will show that a regular $c$-partite tournament with $r \ge 2$ vertices in each partite set contains a cycle with exactly $r-1$ vertices from each partite set, with the exception of the case that $c = 4$ and $r = 2$. (English) |
| Keyword:
|
multipartite tournaments |
| Keyword:
|
regular multipartite tournaments |
| Keyword:
|
cycles |
| MSC:
|
05C20 |
| MSC:
|
05C38 |
| MSC:
|
05C40 |
| idZBL:
|
Zbl 1164.05398 |
| idMR:
|
MR2261656 |
| . |
| Date available:
|
2009-09-24T11:38:30Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128109 |
| . |
| Reference:
|
[1] J. Bang-Jensen, G. Gutin: Digraphs: Theory, Algorithms and Applications.Springer-Verlag, London, 2000. MR 2472389 |
| Reference:
|
[2] L. W. Beineke, C. Little: Cycles in bipartite tournaments.J. Combinat. Theory Ser. B 32 (1982), 140–145. MR 0657682, 10.1016/0095-8956(82)90029-6 |
| Reference:
|
[3] J. A. Bondy: Diconnected orientations and a conjecture of Las Vergnas.J. London Math. Soc. 14 (1976), 277–282. Zbl 0344.05124, MR 0450115 |
| Reference:
|
[4] P. Camion: Chemins et circuits hamiltoniens des graphes complets.C. R. Acad. Sci. Paris 249 (1959), 2151–2152. Zbl 0092.15801, MR 0122735 |
| Reference:
|
[5] W. D. Goddard, O. R. Oellermann: On the cycle structure of multipartite tournaments.In: Graph Theory Combinat. Appl. 1, Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schenk (eds.), Wiley-Interscience, New York, 1991, pp. 525–533. MR 1170802 |
| Reference:
|
[6] Y. Guo: Semicomplete multipartite digraphs: a generalization of tournaments.Habilitation thesis, RWTH Aachen, 1998. |
| Reference:
|
[7] G. Gutin: Cycles and paths in semicomplete multipartite digraphs, theorems and algorithms: a survey.J. Graph Theory 19 (1995), 481–505. Zbl 0839.05043, MR 1333778, 10.1002/jgt.3190190405 |
| Reference:
|
[8] G. Gutin, A. Yeo: Note on the path covering number of a semicomplete multipartite digraph.J. Combinat. Math. Combinat. Comput. 32 (2000), 231–237. MR 1748910 |
| Reference:
|
[9] J. W. Moon: On subtournaments of a tournament.Canad. Math. Bull. 9 (1966), 297–301. Zbl 0141.41204, MR 0200196, 10.4153/CMB-1966-038-7 |
| Reference:
|
[10] L. Rédei: Ein kombinatorischer Satz.Acta Litt. Sci. Szeged 7 (1934), 39–43. |
| Reference:
|
[11] M. Tewes, L. Volkmann, and A. Yeo: Almost all almost regular $c$-partite tournaments with $c \ge 5$ are vertex pancyclic.Discrete Math. 242 (2002), 201–228. MR 1874765, 10.1016/S0012-365X(01)00212-6 |
| Reference:
|
[12] L. Volkmann: Strong subtournaments of multipartite tournaments.Australas. J. Combin. 20 (1999), 189–196. Zbl 0935.05051, MR 1723872 |
| Reference:
|
[13] L. Volkmann: Cycles in multipartite tournaments: results and problems.Discrete Math. 245 (2002), 19–53. Zbl 0996.05063, MR 1887047 |
| Reference:
|
[14] L. Volkmann: All regular multipartite tournaments that are cycle complementary.Discrete Math. 281 (2004), 255–266. Zbl 1049.05043, MR 2047772, 10.1016/j.disc.2003.09.012 |
| Reference:
|
[15] L. Volkmann, S. Winzen: Almost regular $c$-partite tournaments contain a strong subtournament of order $c$ when $c \ge 5$.Submitted. |
| Reference:
|
[16] A. Yeo: One-diregular subgraphs in semicomplete multipartite digraphs.J. Graph Theory 24 (1997), 175–185. Zbl 0865.05045, MR 1425821, 10.1002/(SICI)1097-0118(199702)24:2<175::AID-JGT5>3.0.CO;2-N |
| Reference:
|
[17] A. Yeo: Semicomplete multipartite digraphs.Ph.D. Thesis, Odense University, 1998. Zbl 0916.05049 |
| Reference:
|
[18] A. Yeo: How close to regular must a semicomplete multipartite digraph be to secure Hamiltonicity?.Graphs Combin. 15 (1999), 481–493. Zbl 0939.05059, MR 1735094, 10.1007/s003730050080 |
| Reference:
|
[19] K.-M. Zhang: Vertex even-pancyclicity in bipartite tournaments.Nanjing Daxue Xuebao Shuxue Bannian Kan 1 (1984), 85–88. MR 0765176 |
| . |
