Research On Cycle Structures And Path Structures In Bipartite Graphs

The path and cycle is one of the important research topics of structural graph theory.Research it has not only important theoretical significance,but also widely applied in computer science,information science and life science.It is a NP-hard problem to determine whether a graph is a Hamiltonian.Hamiltonian problem is one of the central problems in graph theory because of its close connection with the four color theorem and its strong applicability.In this thesis,we concentrate on the study of the path structure and cycle structure in bipartite graphs.This thesis consists of four section.In the first section,we give some definitions and notations that we needed in this paper.Then,we introduce the background and significance of the research,including the development at home and abroad regarding this aspect.Based on the discussion of research background and current situation,it fully shows the necessity and innovation of the main research work.In the second section,we mainly study the bipancyclicism and bipanconnectiv-ity of bipartite graphs.In 1975,Alavi and Williamson first proposed the concept of connectivity.Two years later,Williamson proved that a graph G is a panconnected graph that satisfies the minimum degree S(G)>n/2+1 and n is the vertex number of G.In 1989,Tian Feng and Zang Wen’an proved for any x ∈Vi and i ∈ {1,2},if the bipartite graph G satisfies degree condition d(x)|V3-i|/2+1,then G is odd and even panconnected.In 2018,Du et al.proved the bipanconnected of bipartite graph withσ(G)≥ n/2+1 and n=max{|V1|,|V2|}.We generalize these two theorems,prove the bipartite graph that has not less than 1/2 of edge prorating number is bipancon-nected.This paper has published on Applied Mathe,matics a,nd Computation.In this section,we propose a new definition of path two bipancyclic and prove nearly all bipartite graphs with not less than 1/2 of edge prorating number is path two bipancyclic.In the third section,we research the degree condition of weakly chorded bipan-cyclic about bipartite graph.In 1989,Tian and Zang[Bipancyclism in Hamiltonian bipartite graphs,Journal of Systems Science and Complexity 2(1989),22-31]proved that any Hamiltonian bipartite graph on 2n(n≥ 60)vertices with minimum degree larger than 2n/5+2 is bipancyclic.In Section 3,our research improve it and prove if G=(Vi,V2,E)is a 2-connected bipartite graph with min{|Vi|,|V2|}≥ 24 that satisfied δG[Vi]=min{dG(x):x∈Vi}≥|V3-i|/3+5 and i=1,2,then G is a weakly chorded bipancyclic graph of girth 4.The proof of this theorem is complicated,and need various methods to prove the existence of chorded bicycle with different lengths.In Subsection 1,we prove some structural lemma in bipartite graphs.In Subsection 2,we use nested cycle structures to prove the existence of small size chorded bicycle with lengths from 6 to min{2|V1|/3,2|V2|/3}+8.In Subsection 3,we utilize weak connectivity,bipanconnected and nested cycle structures to proof of existence of middle size chorded bicycle with lengths from min{2|V1|/3,2|V2|/3}+10 to min{4|V1|/3,4|V2|/3}.In Subsection 4,we use the contradiction and the analyzing of local structure to show the existence of large size chorded bicycle with lengths from min{4|V1|/3,4|V2|/3} to the circumference.Finally,in Subsection 5,we proof the main theorem.In the fourth section,We elaborate the problems that can be deep considered.