Research On Integer Flow Problem Of Signed Graphs

As a new subject,graph theory has achieved rapid development and been widely applied which benefit from the development of computer science.It has penetrated into physics,chemistry,computer science,information theory,cyber-netics,and many other fields.There are many branches in graph theory,such as Hypergraph theory,extremal graph theory,algorithms graph theory,network graph theory,random graph theory,and so on.In the 1930s,a large number of new theories and new results about graph theory appeared,e.g.Menger Theo-rem,Kuratowski Theorem,R.amsey theorem etc.,which laid good foundations for the further development of graph theory.Among all directions mentioned above,integer flow theory is also an area of focus.Nowhere-zero integer flow on signed graph was first put forward by the Bouchet.He conjectured that a S-bridgeless graph admits a nowhere-zero 6-flow.At the same time he proved that if a signed graph is S-bridgeless,then it has nowhere-zero 216-flow.Later Zyka proved that S-bridgeless signed graph has nowhere-zero 30-flow.Recently,Devos improved the result to nowhere-zero 12-flow.This is regarded as the best result about the conjecture above.By adding some constrains to the signed graph,some better results were achieved.For example,that every S-bridgeless 4-edge-connected signed graph has nowhere-zero 4-flows proved by Andre and Zhu.Inspired by the conclu-sion above,we prove that a nowhere-zero 8-flow is admitted on S-bridgeless Hamiltonian signed graph.In this paper,main content is divided into three chapters.In Chapter 1,we firstly introduce relevant definitions and concepts of graphs,including definitions of signed graphs,integer flows,as well as some concepts and theorems of matroid.In chapter 2,we introduce related conclusion of integer flows on signed graphs.In chapter 3,by introducing some new concepts and proving some useful lemmas,we finally give the proof of the main conclusion:S-bridgeless Hamil-tonian signed graph has nowhere-zero 8-flow.