On The Hamiltonian Decomposition And Universal Arcs In Locally Semicomplete Digraphs

In graph theory,the problems on hamiltonian decomposition and universal arcs are alway the topics for research scholars.As Bang-Jensen proposed the concepts of locally semicomplete digraphs in 1990,the problems on hamiltonian decomposition and universal arcs in locally semicomplete digraphs are widely concerned by researchers.A locally semicomplete digraph without 2-cycle is a local tournament.In 2012,Bang-Jensen and Huang(J Combin Theory Ser.B.2012,102:701-714)concluded that every 2-arc-strong locally semicomplete digraph which is not the second power of an even cycle has two arc-disjoint strong spanning subdigraphs,and proposed the conjecture that every 3-strong local tournament has two arc-disjoint hamiltonian cycles.In this thesis,we discuss arc-disjoint hamiltonian paths and cycles in locally semicomplete digraphs.In 2016,Bai et al.(Discrete Mathematics.2016,339:2063-2065)discusses universal arcs in tournaments,this thesis discusses universal arcs in round digraphs which is a special subclass of locally semicomplete digraphs,and we generalize the result on tournaments to round digraphs.To discuss these problems,this thesis consists of 5 chapters.Chapter 1 is the preface,which contains basic concepts on digraphs and research back-ground on related problems.Round digraphs is a special subclass of locally semicomplete digraphs.It is always the beginning for scholars to study the problems of locally semicomplete digraphs.In Chapter 2,we discuss the arc-disjoint hamiltonian paths and cycles in a round digraph,and prove the following:(a)every 2-strong round digraph contains one hamiltonian path and one hamiltonian cycle which are disjoint if and only if it is not a second power of an even cycle.(b)every 3-strong round digraph contains two arc-disjoint hamiltonian cycles(c)every 4-strong round digraph contains one hamiltonian cycle and two hamiltonian paths,such that they are arc-disjoint pairwise.(d)those results of round digraphs can be generalized to positive-round digraphs.In Chapter 3,we discuss arc-disjoint hamiltonian paths and cycles in round decom-posable locally semicomplete digraphs,and prove that every 3-strong round decomposable locally semicomplete digraph has two arc-disjoint hamiltonian cycles,which implies that Bang-Jensen and Huang's conjecture holds for the round decomposable local tournaments.Also,we characterize all 2-strong round decomposable local tournaments each of which con-tains a hamiltonian path P and a hamiltonian cycle arc-disjoint from P.In Chapter 4,we discuss arc-disjoint hamiltonian paths in non-round decomposable local tournament,and prove that every 2-strong non-round decomposable local tournament which is not a tournament contains a pair of arc-disjoint hamiltonian paths with distinct initial vertices and terminal vertices.Also this result combining with the one on arc-disjoint hamiltonian cycles of round decomposable local tournaments generalizes a result(every 2-strong tournament has two arc-disjoint hamiltonian paths with distinct initial vertices and distinct terminal vertices)from Thomassen for tournaments.In Chapter 5,an arc uv is called universal if uv and w are in a common cycle for any vertex w of D.We prove that every arc of a round digraph R is universal if and only if R is a cycle or R is an exceptional class of 2-strong round digraphs.We also give a polynomial algorithm to recognize whether each arc of a round digraph is universal.