| The theory of hamiltonian cycles in graph is a very popular research field,the hamiltonian cycle problem leads to similar problems such as the TSP,CPP.The research of this kind of problems have promoted the research of optimization methods and the development of Operations Research and Topology.The sufficient and necessary conditions for Hamiltonian cycles in graphs have not been found.Multipartite digraphs are the important part of digraphs.In the past,the study of multipartite digraphs focused on multipartite tournaments and almost regular multipartite digraphs,but there are very few studies on the degree condition.In recent years,the research on the degree condition of the bipartite digraphs have made a breakthrough,but it is still need to be improved.In this paper,we mainly study that the existence of long cycles in unbalanced bipartite digraphs and hamiltonian cycles in balanced 3-partite digraphs.The thesis consists of three chapters.Chapter 1 is the preface.In this chapter,we introduce the background and the development of hamiltonian problem.In Chapter 2,we study the half-degree sum condition for cycles of covering all vertices in the smaller part set in unbalanced bipartite digraphs.In 2012,Adamus et al.gave the half-degree sum condition for the existence of hamiltonian cycles in a balanced bipartite digraph and proposed the following conjecture:Let D be a bipartite digraph with colour classes X and Y such that |X|=α ≤b=|Y|.If d+(x)+d-(y)>a+b+2/2 where x and y lie in opposite colour classes and xy (?) A(D),then D contains an oriented cycle of length 2a.Let b=a+k.Then d+(x)+d-(y)>a+b+2/2 is equivalent to d+(x)+d-(y)≥ a+2+k-1/2.In this chapter,we strengthen the degree condition in the conjecture.We prove the theorem:Let D be a bipartite digraph with colour classes X and Y such that |X|=α≤b=|Y|,b=a+k,α≥ 2,k≥ 3.If D satisfies one of the following conditions,then D contains an oriented cycle of length 2a.(ⅰ)If d+(x)+d-(y)≥ α+k where x and y lie in opposite colour classes and xy(?)A(D);(ⅱ)If d+(x)+d-(y)≥α+2+k-1/2 where x and y lie in opposite colour classes and xy(?) A(D)and d+(u)+d-(v)≥ α+1 where u,v∈Y.In Chapter 3,we study the half-degree sum condition for a balanced 3-partite digraph to be hamiltonian.In 2012,Adamus et al.gave the half-degree sum condition for the existence of hamiltonian cycle in a balanced bipartite digraph,Let D be a balanced bipartite digraph with colour classes X and Y of cardinalities a,where a≥ 2.If d+(x)+d-(y)≥ a+2 where x and y lie in opposite colour classes and xy(?) A(D),then D contains an oriented cycle of length 2a.In this chapter,we extend to balanced 3-partite graphs,prove the theorem:Let D=(V1,V2,V3)be a balanced 3-partite digraph of order 3a.If for any two nonadjacent vertices x∈Vi,v∈Vj(i≠j)and xy(?) A(D),dVj+(x)+dVi-(y)≥ a+2,then D is hamiltonian. |
