Cycles with a given number of vertices from each partite set in regular multipartite tournaments

Lutz Volkmann; Stefan Winzen

Czechoslovak Mathematical Journal (2006)

  • Volume: 56, Issue: 3, page 827-843
  • ISSN: 0011-4642

Abstract

top
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 ∈ ℕ 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 ≥ 3 , then we will show that a regular c -partite tournament with r ≥ 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 .

How to cite

top

Volkmann, Lutz, and Winzen, Stefan. "Cycles with a given number of vertices from each partite set in regular multipartite tournaments." Czechoslovak Mathematical Journal 56.3 (2006): 827-843. <http://eudml.org/doc/31070>.

@article{Volkmann2006,
abstract = {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$.},
author = {Volkmann, Lutz, Winzen, Stefan},
journal = {Czechoslovak Mathematical Journal},
keywords = {multipartite tournaments; regular multipartite tournaments; cycles; multipartite tournaments; regular multipartite tournaments; cycles},
language = {eng},
number = {3},
pages = {827-843},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Cycles with a given number of vertices from each partite set in regular multipartite tournaments},
url = {http://eudml.org/doc/31070},
volume = {56},
year = {2006},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 56
IS - 3
SP - 827
EP - 843
AB - 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$.
LA - eng
KW - multipartite tournaments; regular multipartite tournaments; cycles; multipartite tournaments; regular multipartite tournaments; cycles
UR - http://eudml.org/doc/31070
ER -

References

top
  1. Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London, 2000. (2000) MR2472389
  2. 10.1016/0095-8956(82)90029-6, J.  Combinat. Theory Ser.  B 32 (1982), 140–145. (1982) MR0657682DOI10.1016/0095-8956(82)90029-6
  3. Diconnected orientations and a conjecture of Las Vergnas, J. London Math. Soc. 14 (1976), 277–282. (1976) Zbl0344.05124MR0450115
  4. Chemins et circuits hamiltoniens des graphes complets, C. R.  Acad. Sci. Paris 249 (1959), 2151–2152. (1959) Zbl0092.15801MR0122735
  5. 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. (1991) MR1170802
  6. Semicomplete multipartite digraphs: a generalization of tournaments, Habilitation thesis, RWTH Aachen, 1998. (1998) 
  7. 10.1002/jgt.3190190405, J.  Graph Theory 19 (1995), 481–505. (1995) Zbl0839.05043MR1333778DOI10.1002/jgt.3190190405
  8. Note on the path covering number of a semicomplete multipartite digraph, J. Combinat. Math. Combinat. Comput. 32 (2000), 231–237. (2000) MR1748910
  9. 10.4153/CMB-1966-038-7, Canad. Math. Bull. 9 (1966), 297–301. (1966) Zbl0141.41204MR0200196DOI10.4153/CMB-1966-038-7
  10. Ein kombinatorischer Satz, Acta Litt. Sci. Szeged 7 (1934), 39–43. (1934) 
  11. 10.1016/S0012-365X(01)00212-6, Discrete Math. 242 (2002), 201–228. (2002) MR1874765DOI10.1016/S0012-365X(01)00212-6
  12. Strong subtournaments of multipartite tournaments, Australas. J.  Combin. 20 (1999), 189–196. (1999) Zbl0935.05051MR1723872
  13. Cycles in multipartite tournaments: results and problems, Discrete Math. 245 (2002), 19–53. (2002) Zbl0996.05063MR1887047
  14. 10.1016/j.disc.2003.09.012, Discrete Math. 281 (2004), 255–266. (2004) Zbl1049.05043MR2047772DOI10.1016/j.disc.2003.09.012
  15. Almost regular c -partite tournaments contain a strong subtournament of order  c when c ≥ 5 , Submitted. 
  16. 10.1002/(SICI)1097-0118(199702)24:2<175::AID-JGT5>3.0.CO;2-N, J.  Graph Theory 24 (1997), 175–185. (1997) Zbl0865.05045MR1425821DOI10.1002/(SICI)1097-0118(199702)24:2<175::AID-JGT5>3.0.CO;2-N
  17. Semicomplete multipartite digraphs, Ph.D. Thesis, Odense University, 1998. (1998) Zbl0916.05049
  18. 10.1007/s003730050080, Graphs Combin. 15 (1999), 481–493. (1999) Zbl0939.05059MR1735094DOI10.1007/s003730050080
  19. Vertex even-pancyclicity in bipartite tournaments, Nanjing Daxue Xuebao Shuxue Bannian Kan 1 (1984), 85–88. (1984) MR0765176

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.