The Supereulerianity Of Several Classes Of Digraphs

The graph theory originated in the maze and the game,has more than 200 years of history.The most representative is the problem of the Seven Bridges of Konigsberg which was solved by mathematician Euler in 1736.Later,people used the knowledge of graph theory to try to solve some problems in other disciplines,especially Kirchhoff solved the problem of simultaneous equations by using the knowledge of trees in graph theory.After entering the middle of twentieth century,with the advent of the first computer in the world,the development of graph theory has been developing rapidly,and has been widely applied in physics,operations research and other disciplines.At the same time,in daily life,there are many problems that can be solved by graph theory and methods,for example,the least time to complete tasts and the shortest path problemIn 1977,Boesch,Suffel and Tindell et al.proposed supereulerian problem according to the Chinese postman problem.Supereulerian digraph refers to contain a spanning eulerian subdigraph.The property of being supereulerian digraph is at the same time a relaxation of being eulerian digraph and of being hamiltonian digraph:being supereulerian means having a closed walk covering all the vertices without using an arc twice;being eulerian means having a closed walk covering all the arcs without using an arc twice;being hamiltonian means having a closed walk covering all the vertices without using a vertex twice.In real life,the application of supereulerian(di)graph is very extensive,such as make a travel plan,courier express delivery etcIn this paper,we focus on the supereulerian property of the digraph,and mainly study the supereulerian properties of several classes of digraphsThe first chapter,the main background and significance of research on this topic,and as of now supereulerian in the domestic and foreign development status and research achieve-ments are introduced,and the related basic concepts are introducedIn the second chapter,we give sufficient and necessary conditions involving path-mergeable digraphs and semicomplete digraphs to be supereulerian.The method of finding the contradiction by using the maximum closed ditrail is proved that if is a path-mergeable digraph or a semicomplete digraph,then it is supereulerian if and only if it is strong con-nected.In the third chapter,Bang-Jensen and Thomasse conjectured that if the arc-strong con-nectivity ?(D)of a digraph D is not less than the independence number ?(D),then D is supereulerian.In this chapter,we prove that if D is an extended cycle,an extended hamil-tonian digraph,an arc-locally semicomplete digraph,an entended arc-locally semicomplete digraph,an extension of two kinds of eulerian digraph,a hypo-semicomplete digraph or an extended hypo-semicomplete digraph satisfying ?(D)??(D),then D is supereulerianIn the fourth chapter,we obtain sufficient conditions on digraph to be supereulerian for given diameter.First,we give a counter example of non supereulerian digraph with diam(D)?3,and then prove that if a digraph D with diam(D)?2,then D is supereulerian Finally,we proved that for a bipartite digraph D,if diam(D)?3,then it is supereulerian.