Bypasses In Digraphs

Graph Theory originates from the Seven Bridges of Konigsberg problem.Euler published the first graph theory paper.Graph Theory has developed rapidly in the past 200 years.Graph Theory does not make progresses only in theory but also in the practical application.Graph Theory becomes more and more popular in scholar.Using the artful method and classic graphs to solve the profound and complex problem is one of the characteristics of Graph Theory.The concepts and results of Graph Theory come from many sources such as practical application and theory research.The content of Graph Theory is wide and abundant which covers Graph Coloring Problem and Supereulerian problem and so on.Inspired by the sufficient conditions of diagraphs contain a Hamiltonian bypass,we give the definition of Supereulerian bypass.Using the classified discussion we got the sufficient condition of digraphs contain a Supereulerian bypass.In the same time,we proved that regular ordinary m-partite(m? 5)tournament and almost regular ordinary m-partite(m?10)tournament have a k-bypass from a to v.We also got some corollaries about the existence of Hamiltonian bypass and Supereulerian bypass in m-partite(m? 5)tournament.In this dissertation,we will discuss the k-bypass of digraph problem.Let D be a digraph and ?(D)be the arc-strong connectivity of D,?'(D)be the size of a maximum matching of D.If(u,v)?D and P is a path of length k from u to v,then P is called a k-bypass from u to v.In this paper we show that(1)a strong digraph D and ?(D)??'(D)? 5,then D contains a Supereulerian bypass(i.e.,a subdigraph is obtained from a spanning eulerian subdigraph by reversing exactly one arc).(2)T is a regular ordinary m-partite(m? 5)tournament.If(u,v)?T,there is a k-bypass from u to v,3?k?|V(T)|-1.(3)T is an almost regular ordinary m-partite(m?0)tournament.If(u,v)?T,there is a k-bypass from a to v,3?k?| V(T)|-1.(4)Every balanced extended arc-3-cyclic and 3-connected tournament contains a Supereulerian bypass.