Font Size: a A A

On Vertex-Disjoint Cycles In Tournaments

Posted on:2020-01-20Degree:MasterType:Thesis
Country:ChinaCandidate:S ZhuFull Text:PDF
GTID:2370330572490723Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
In this paper,we investigate the problems of vertex-disjoint cycles in tournamentsThis paper consider only digraph.For a digraph D,we write V(D)for the vertex set of D,and the order of D is the cardinality of V(D).We write A(D)for the set of the arcs of D.Let T = T(V(T),A(T))be a tournament.The order of T is V(T)and its set of the arcs of T is A(T).We say that the cycle C is a q-cycle if |V(C)| = q.A tournament is a digraph T such that for any two distinet vert.ices x and y,exactly one of the order pairs(x,y)and(y,x)is an arc of T,Let v e V(T),then the out-degree of v is denoted by d?(v),and the minimum out-degree of T is denoted by ?+(T).In 1981,Bermond and Thomassen proposed a conjecture:for any positive integer k,any digraph of minimum out-degree at least 2k--1 contains at least k disjoint directed cycles.It is trivially when k?1.It was proved by Thomassen when k?2 in 1983.The case k =3 was proved by Lichiardopol et al.It is still open for large values of k.In 2014,Jorgen Bang-Jensen,Bessy and Thomasse proved the conjecture for tournaments.In 2010,Lichiardopol proposed a conjecture for tournaments:for given q?3 and k?1,a tournament T with minimum out-degree at least(q-1)k-1 contains at,least.k disjoint q-cycles.In the same paper,Lichiardopol himself proved the case that both the minimum out--degree and minimum in-degree are at least(q-1)k-1.In 2018,F.Ma and J.Yan improve this results by giving two theorems.Inspired by this,we prove the following results,it is a solution of Lichiardopol's conjecture when taking q = 4Result 1:For an integer k?1,every tournament T with ??(T)?3k-1 contains k vertex-disjoint 4-cyclesActually we make the following much stronger resultResult 2:For every tournament,T with ??(T)?3k-1 and every collection F of k-1 vertex-disjoint,4-cycles of T,there exists a collection of k vertex-disjoint 4-cycles of T which intersects T-F on at most seven vertices.
Keywords/Search Tags:Tournament, Minimum Out-degree, Disjoint Cycles, Digraph
PDF Full Text Request
Related items