The Longest Cycles And Paths In Degree-Constrained Bipartite Digraphs

In graph theory,the problems related to the Hamiltonian cycles and Hamiltonian paths are of the key points.As Dirac and Ore linked Hamiltonian cycles with degree-constrained conditions,the degree-constrained conditions of digraphs have also become the focus of researchers.The bipartite digraphs are important class of digraphs.The hamiltonicity of bipartite digraphs is widely concerned by digraph scholars.we study the existence of the maximum cycles,Hamiltonian cycles and Hamiltonian paths in degree-constrained bipartite digraphs.The thesis consists of four chapters.In Chapter 1,we introduce the application background and some basic concepts related to this paper.In Chapter 2,we study the existence of the longest cycles in bipartite digraphs with a semi-degree condition.We prove the following result.Let D be a bipartite digraph with bipartition X and Y such that |X| = a and |Y|=a+k,where a>2 and k= 1 or k=2.If where u and v lie in opposite bipartition and uv(?)A(D),then D contains a cycle of length at least a.In Chapter 3,we study the existence of the Hamiltonian cycles in strong balanced bipartite digraphs with a degree condition on dominating pairs.We prove the following result.Let D be a strong balanced bipartite digraph on 2a vertices where a>2.Suppose that,for every dominating pair of vertices {x,y},either d(x)?2a-2 and d(y)? a + 2 or d(x)? a+ 2 and d(x)? 2a-2.Then D is Hamiltonian.In Chapter 4,we study the existence of the Hamiltonian cycles in balanced bipartite digraphs with a degree sum condition.We prove the following result.Let D be a strong balanced bipartite digraph on 2a vertices where a>2.If d(u)+ d(v)? 3a-1,for every pair of distinct vertices u,v ? V(D)such that u and v are not adjacent,then D contains a Hamiltonian path.The bound of this theory is sharp.