Some Sufficient Conditions For A Digraph To Be Hamiltonian

Digraph is an important branch of graph theory.The hamiltonicity of digraphs is a basic problem of graph theory,and it has a very wide range of applications in real life.For more than half a century,people have studied hamiltonian problem deeply and many important results have been achieved.This paper mainly focuses on the hamiltonicity of strong digraphs and balanced bipartite digraphs.The thesis consists of four chapter.Chapter 1 is the preface.In this chapter,we introduce the background,the development of hamiltonian problem and present the basic concept which will be used.In Chapter 2,we study the dominated pair degree condition for a digraph to be hamil-tonian.In 1996,Bang-Jensen,Gutin,and Li proposed the following conjecture:If D is a strong digraph of order n where n? 2 with the property that d(x)+d(y)?2n-1 for every pair of dominated non-adjacent vertices {x,y},then D is hamiltonian.In this chapter,we give an infinite family of counterexamples to prove that this conjecture is wrong.We also prove that this conjecture is also wrong when the condition is strengthened to d(x)?2n-4,d(y)?3 or d(x)?3,d(y)?2n-4 for every pair of dominated non-adjacent vertices.In Chapter 3,we study the dominating pair and dominated pair degree condition for a digraph to be hamiltonian.Bang-Jensen,Gutin,and Li proposed the following conjecture:If D is a strong digraph of order n where n?2 with the property that d(x)+d(y)?2n-1 for every pair of dominating non-adjacent and every pair of dominated non-adjacent vertices{x,y},then D is hamiltonian.This conjecture is still public.In this chapter,we further propose a conjecture:There is an integer 1 ?k ?n-5 such that every strong digraph of order n satisfying the condition d(x)?n+k,d(y)?n-1 or d(x)?n-1-k,d(y)?n+k for every pair of dominating non-adjacent and every pair of dominated non-adjacent vertices{x,y},is hamiltonian.We prove that it is correct when k=n-5,n-6,n-7.This conclusion also partially solves the above conjecture.In Chapter 4,we study the hamiltonicity of balanced bipartite digraphs.In 2012,Adamus et al.proved the theorem:Let D be a balanced bipartite digraph of order 2a,if d+(u)+d-(v)?a+2 for all pair of vertices u and v with uv(?)A(D),then D is hamiltonian.The author also give a digraph of order 6 to prove that the lower bound is tight.In this chapter,we reduce its lower bound to a+1,and prove that D is either hamiltonian or isomorphic to the above digraph of order 6.From this,we determine the extermal digraph of above theorem.