Cycles through a given set of vertices in regular multipartite tournaments

다국어 초록 (Multilingual Abstract)

A tournament is an orientation of a complete graph, and in generala multipartite or c-partite tournament is an orientation of acomplete c-partite graph.In a recent article, the authors proved that a regular c-partitetournament with r ge 2 vertices in each partite set contains acycle with exactly r-1 vertices from each partite set, withexception of the case that c = 4 and r = 2. Here we willexamine the existence of cycles with r-2 vertices from eachpartite set in regular multipartite tournaments where the r-2vertices are chosen arbitrarily. Let D be a regular c-partitetournament and let X subseteq V(D) be an arbitrary set withexactly 2 vertices of each partite set. For all c ge 4 wewill determine the minimal value g(c) such that D-X isHamiltonian for every regular multipartite tournament with r geg(c).

참고문헌 (Reference)

1 "Theory of graphs" 1962

2 "Strong subtournaments of multipartite tournaments" 20 : 189-196, 1999

3 "Semicomplete Multipartite Digraphs:A Generalization ofTournaments" 102-, 1998

4 "Semicomplete Multipartite Digraphs" 1998

5 "One-diregular subgraphs in semicomplete multipartite digraphs" 24 (24): 175-185, 1997

6 "On the connectivity of close to regular multipartite tournaments" 154 (154): 1437-1452, 2006

7 "On subtournaments of a tournament" 297-, 1966

8 "Note on the path covering number of a semicomplete multipartite digraph" 32 : 231-237, 2000

9 "How close to regularmust a multipartite tournament be to secure a given path covering number?"

10 "How close to regular must a semicomplete multipartite digraph be to secure Hamiltonicity ?" 15 (15): 481-493, 1999

11 "Fundamente der Graphentheorie,Springer Lehrbuch Mathematik" Sprin-ger-Verlag, Vienna 1996

12 "Eine Extremalaufgabe aus der Graphentheorie" 436-48, 1941

13 "Digraphs,Theory, algorithms and applications. Springer Monographs in Mathematics" Springer-Verlag London, Ltd., London 2001

14 "Cycles with a given number of vertices from each partite set in regular multipartite tournaments" 56 (56): 827-843, 2006

15 "Cycles in multipartite tournaments: results and problems" 245 (245): 19-53, 2002

16 "Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms : a survey" 19 (19): 481-505, 1995

17 "Close to Regular Multipartite Tournaments" 2004

18 "Almost regular c-partite tournaments contain a strong subtournaments of orderc when cgeq 5"