Research On Supereulerian Digraphs

Digraph is an important branch of graph theory.The eulerian and hamiltonian properties of digraphs are two classical research topics in digraphs.A digraph is supereulerian if it contains a spanning eulerian subdigraph.In particular,both eulerian digraphs and hamiltonian digraphs are supereulerian digraphs,so the property of being supereulerian is at the same time a relaxation of being eulerian and of being hamiltonian.This thesis mainly studies the supereulerian property of digraphs.There are four chapters in this dissertation,which are organized as follows.In Chapter 1,we introduce the related background and significance,research status and progresses at home and abroad,and related basic concepts.In Chapter 2,around the conjecture put forward by Bang-Jensen et al.:if the arc-strong connectivity λ(D)of a digraph D is not smaller than its independence number α(D),then D is supereulerian;we give a sufficient and necessary condition involving 3-path-quasi-transitive digraphs to be supereulerian and prove that the conjecture is ture for 3-path-quasi-transitive digraphs.For any distinct four vertices c1,c2,c3,c4 of a digraph D,D is H1-quasi-transitive if {(c1,c2),(c3,c2),(c4,c3)}(?)A(D),c1 and c4 are adjacent;D is H2-quasi-transitive if {(c2,c1),(c2,c3),(c3,c4)}(?) A(D),c1 and c4 are adjacent;D is H3-quasi-transitive if {(c1,c2),(c2,c3),(c3,c4)}(?) A(D),c1 and c4 are adjacent;D is H4-quasi-transitive if {(c1,c2),(c3,c2),(c3,c4)}(?) A(D),c1 and c4 are adjacent.There are four distinct possible orientations of a 3-path,therefore we will refer to Hi-quasi-transitive digraphs as 3-path-quasitransitive digraphs for convenience,where 1≤i≤4.In Chapter 3,we investigate the sufficient Ore type condition for a digraph to be supereulerian.We first show that a strong digraph D with n vertices is supereulerian if for every three different vertices z,w and v such that z and w are nonadjacent,d(z)+d(w)+d+(z)+d-(v)≥3n-5(if(z,v)(?)A(D))and d(z)+d(w)+d-(z)+d+(v)≥3n-5(if(v,z)(?)A(D)).And this bound is sharp.Moveover we prove that a 2-strong digraph D with n vertices is supereulerian if for any two distinct pairs of nonadjacent vertices{u,v} and {w,z},d(u)+d(v)+d(w)+d(z)≥4n-7.Furthermore,we show that if a strong but not 2-strong digraph D satisfies the above condition,then D is not necessarily supereulerian but has a spanning ditrail.In Chapter 4,we explore the degree(sum)conditions on any pair of dominated or dominating nonadjacent vertices for a digraph to be supereulerian.We first propose the following conjecture:there exists an integer t with 0≤t≤n-3 so that any strong digraph with n vertices satisfying either both d(u)≥n-1+t and d(v)≥n-2-t or both d(u)≥n-2-t and d(v)≥n-1+t,for any pair of dominated or dominating nonadjacent vertices{u,v},is supereulerian.We prove that the conjecture holds for t=0,t=n-4 and t=n-3.Moreover,we establish the following conjecture analogous to the above:if a strong digraph D with n vertices satisfies d(u)+d(v)≥2n-3 for any pair of dominated nonadjacent vertices{u,v} of D,then D is supereulerian.(If this conjecture is true,then it can directly deduce the theorem of Bang-Jensen et al.[1].)We prove that the conjecture holds for semicomplete multipartite digraphs.Furthermore,we show that if a strong digraph D with n vertices satisfies min{d+(u)+d-(v),d-(u)+d+(v)}≥n-1 for any pair of dominated or dominating nonadjacent vertices {u,v} of D,then D is supereulerian.Finally,we show that if a strong digraph D with n vertices satisfies d(u)+d(v)≥2n-3 and min{d-(u)+d+(v),d+(u)+d-(v)}≥n-2,or satisfies d(u)+d(v)≥5/2n-11/2,for any pair of dominated or dominating nonadjacent vertices{u,v} of D,then D is supereulerian.All our results in this chapter are best possible by giving an example.