Spanning Subdigraphs In Semicomplete Digraphs

Let D=(V,A)be a digraph.A digraph D is a semicomplete digraph if there is at least one arc between any pair of distinct vertices of D.A digraph D is a tournament if there is precisely one arc between any pair of distinct vertices of D.A subdigraph of D is called a spanning subdigraph if it contains all vertices of D.In this thesis,we consider the spanning subdigraphs in semicomplete digraphs.Let k be a positive integer.A digraph is strongly connected if it has a directed path from x to y for every ordered pair of distinct vertices x,y and it is strongly k-connected if it has at least k+1 vertices and remains strongly connected when we delete any set of at most k-1 vertices.We use δ+(D),δ-(D)and δ0(D)to denote the minimum out-degree,the minimum in-degree and the minimum semi-degree of D,respectively.The order of D is the number of its vertices.In a highly strong semicomplete digraph,we obtain a spanning tournament by deleting one are from every cycle of length 2,then is the spanning tournament highly strong?This is an interesting problem.Bang-Jensen and Jordán[7]conjectured every(2k-1)strong semicomplete digraph of order n≥2k+1 contains a spanning k-strong tournament.It was proved for k=1 and k=2.In this paper,we show the following results.Result 1.Let D be a semicomplete digraph of order n≥9.If D is 5-strong,then it contains a spanning 3-strong tournament.Result 2.Let D be a(2k-1)-strong semicomplete digraph.If δ+(D)≥3k-2,then it contains a spanning k-strong tournament.A tournament T is transitive if,for every pair xy and yz of arcs in T,the arc xz is also in T.Let To be a tournament on 7 vertices,which contains no transitive subtournament on 4 vertices.Cycle factor is a spanning subdigraph,which consists of some vertex-disjoint cycles.Li and Shu[30]proved that for every strong tournament T of order n>6,if max{δ-(T),δ+(T)}≥3 and T(?)T0,then T has a cycle factor with exactly two cycles.Further,we consider the length of the cycles of cycle factor,we show the following result.Result 3.Let T be a strong tournament of order n≥7 such that T(?)T0.Ifδ0(T)≥ 3,then T has a cycle factor with exactly two cycles such that two cycles has the length 3 and(n-3),respectively.