Some Degree Conditions For A Balanced Bipartite Digraph To Be Hamiltonian

Digraphs are very important in the study of graph theory.The hamiltonian cycle problem and many related problems have been studied extensively for more than half a century,and many remarkable conclusions have been reached.In this paper,we mainly study that the existence of hamiltonian cycle on balanced bipartite digraphs under a dominating pair degree condition,the extremal digraphs for hamiltonian cycles under the other two kinds of degree sum conditions,and the balanced bipartite digraphs are almost bipancyclic on a dominating and dominated pair degree condition.The thesis consists of four Chapters.Chapter 1 is the preface.The basic concepts and application background are introduced.And the main content of this thesis is proposed.In Chapter 2,we study the existence of hamiltonian cycle on balanced bipartite digraphs under a dominating pair degree condition.In 2017,Wang Ruixia gives a sufficient condition for the existence of hamiltonian cycle in balanced bipartite digraphs and puts forward the following problem:for a strong balanced bipartite digraph D of order 2a,if for every pair of dominating vertices {x,y},either d(x)?2a-k,d(y)?a+k or d(x)?a+k,d(y)?2a-k,where 2?k?a/2,is D hamiltonian?This chapter proves that if k of the above problem satisfies max{1,a/4} ?k?a/2,then D is hamiltonian,namely the following theorem:Let D be a strong balanced bipartite digraph of order 2a.If for every pair of dominating vertices {x,y}either d(x)?2a-k,d(y)?a+k or d(x)?a+k,d(y)?2a-k,where max{1,a/4}<k?a/2,then D is hamiltonian.In Chapter 3,the extremal digraphs for hamiltonian cycles are completely characterized under the degree condition from the same partite set and a dominating and dominated pair degree condition in balanced bipartite digraphs.In 2014,Adamus et al.gave a sufficient condition of nonadjacent vertex degree sum for the existence of hamiltonian cycle in balanced bipartite digraphs and showed that the lower bound of this condition is tight.In 2017,Adamus gave a dominating and dominated pair sufficient condition for the existence of hamiltonian cycles in balanced bipartite digraphs and showed that the lower bound of the conditions is tight.In this chapter,by reducing the above bound by 1,we completely describe 5 classes extremal digraphs for hamiltonian cycles in balanced bipartite digraphs,that is,we give the following theorem:Let D be a strong balanced bipartite digraph on 2a vertices,where a>3.If d(u)+d(v)?3a-1 for every pair of dominating and every pair of dominated vertices {x,v},then D is either hamiltonian,or isomorphic to a digraph in H1,or isomorphic to the digraphs H2,H3,H4 Or H5.In Chapter 4,we study that the balanced bipartite digraphs are almost bipan cyclic on a dominating and dominated pair degree condition.In 2018,Adamus gave a Meyniel sufficient condition for the existence of hamiltonian cycle in balanced bipartite digraphs and proposed the following problem:If for every 1?l<a there is a k?1 such that every strong balanced bipartite digraph on 2a vertices contains cycles of all even length up to 2l,provided d(u)+d(v)?3a-k for every pair of dominating and every pair of dominated vertices {u,v}.In this chapter,we will solve this problem by proving the following theorem:Let D be a strong balanced bipartite digraph on 2a vertices,where a>4.If d(u)+d(v)?3a-1 for every pair of dominating and every pair of dominated vertices {u,v},then D either contains cycles of lengths 2,4,…,2a-2,or is a directed cycle of length 2a.