Geodesic
Cycles with a given number of vertices from each partite set in regular multipartite tournaments
Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 827-843
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
Classification : 05C20, 05C38, 05C40
Keywords: multipartite tournaments; regular multipartite tournaments; cycles 
@article{CMJ_2006_56_3_a2,
     author = {Volkmann, Lutz and Winzen, Stefan},
     title = {Cycles with a given number of vertices from each partite set in regular multipartite tournaments},
     journal = {Czechoslovak Mathematical Journal},
     pages = {827--843},
     year = {2006},
     volume = {56},
     number = {3},
     mrnumber = {2261656},
     zbl = {1164.05398},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a2/}
}
TY  - JOUR
AU  - Volkmann, Lutz
AU  - Winzen, Stefan
TI  - Cycles with a given number of vertices from each partite set in regular multipartite tournaments
JO  - Czechoslovak Mathematical Journal
PY  - 2006
SP  - 827
EP  - 843
VL  - 56
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a2/
LA  - en
ID  - CMJ_2006_56_3_a2
ER  - 
%0 Journal Article
%A Volkmann, Lutz
%A Winzen, Stefan
%T Cycles with a given number of vertices from each partite set in regular multipartite tournaments
%J Czechoslovak Mathematical Journal
%D 2006
%P 827-843
%V 56
%N 3
%U http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a2/
%G en
%F CMJ_2006_56_3_a2
Volkmann, Lutz; Winzen, Stefan. Cycles with a given number of vertices from each partite set in regular multipartite tournaments. Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 827-843. http://geodesic.mathdoc.fr/item/CMJ_2006_56_3_a2/

[1] J. Bang-Jensen, G. Gutin: Digraphs: Theory, Algorithms and Applications. Springer-Verlag, London, 2000. | MR

[2] L. W. Beineke, C. Little: Cycles in bipartite tournaments. J.  Combinat. Theory Ser.  B 32 (1982), 140–145. | DOI | MR

[3] J. A. Bondy: Diconnected orientations and a conjecture of Las Vergnas. J. London Math. Soc. 14 (1976), 277–282. | MR | Zbl

[4] P. Camion: Chemins et circuits hamiltoniens des graphes complets. C. R.  Acad. Sci. Paris 249 (1959), 2151–2152. | MR | Zbl

[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

[6] Y. Guo: Semicomplete multipartite digraphs: a generalization of tournaments. Habilitation thesis, RWTH Aachen, 1998.

[7] G. Gutin: Cycles and paths in semicomplete multipartite digraphs, theorems and algorithms: a survey. J.  Graph Theory 19 (1995), 481–505. | DOI | MR | Zbl

[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

[9] J. W. Moon: On subtournaments of a tournament. Canad. Math. Bull. 9 (1966), 297–301. | DOI | MR | Zbl

[10] L. Rédei: Ein kombinatorischer Satz. Acta Litt. Sci. Szeged 7 (1934), 39–43.

[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. | DOI | MR

[12] L. Volkmann: Strong subtournaments of multipartite tournaments. Australas. J.  Combin. 20 (1999), 189–196. | MR | Zbl

[13] L. Volkmann: Cycles in multipartite tournaments: results and problems. Discrete Math. 245 (2002), 19–53. | MR | Zbl

[14] L. Volkmann: All regular multipartite tournaments that are cycle complementary. Discrete Math. 281 (2004), 255–266. | DOI | MR | Zbl

[15] L. Volkmann, S. Winzen: Almost regular $c$-partite tournaments contain a strong subtournament of order  $c$ when $c \ge 5$. Submitted.

[16] A. Yeo: One-diregular subgraphs in semicomplete multipartite digraphs. J.  Graph Theory 24 (1997), 175–185. | DOI | MR | Zbl

[17] A. Yeo: Semicomplete multipartite digraphs. Ph.D. Thesis, Odense University, 1998. | Zbl

[18] A. Yeo: How close to regular must a semicomplete multipartite digraph be to secure Hamiltonicity?. Graphs Combin. 15 (1999), 481–493. | DOI | MR | Zbl

[19] K.-M.  Zhang: Vertex even-pancyclicity in bipartite tournaments. Nanjing Daxue Xuebao Shuxue Bannian Kan 1 (1984), 85–88. | MR