The Problem Of Paths And Cycles In Multipartite Tournaments And Strong Tournaments

It has a long history about the Graph theory and still has a lot of research so far. In this paper,the problems of paths and complementary cycles in almost regular multipartite tournaments, the number of h(t) in strong tournaments are discussed. This paper is composed of three chapters.In the first chapter,the main concept is introduction, we introduce some back-ground of graph theory and the main research contents, method. In the second chapter, we study the problem of complementary cycles in almost regular multi-partitc tour-naments. The main results are:(1)Let D be an multi-partite tournaments of order n, B={b1,b2…bk} be a set of k path-extendible arcs in D,if13ig(D)+108k-198+11Vmax(D)<5n, then there exists a path in D, containing all arcs in B and with|A(P)|≤6k-5(k≥1).(2)Let D be an c-partite tournaments of order n, B={b1,b2…bk} be a set of k path-extendible arcs in D, P be a path, containing all arcs in B, if23ig(D)+19VVmax(D)+30|P|-150<7n, then there exists a longest pathP.(3)Let D be an c-partite tournaments of order n, c≥7, if n>449ig(D)+6728, then for every arc e∈A(D), there exists a cycIe of length l containing e, for all6<l<n.(4)Let D be an c-partite tournaments of order n, c≥5,if n>55ig(D)+7,then every vertex in D lies on4-cycle.In the third chapter,we study the complementary cycles in almost regular4-part tournaments and the number of h(t) in strong tournaments. The main results are:(1) Let D be an almost regular c-partite tournaments,|V(D)|≥8, then D contain a pair of complementary cycles, except D isomorphic D4,2.(2) For every strorlg tournaments, h(t)≥3.