Research On Parameters And Cycle Structures In Bipartite Graphs

The determination of a Hamilton graph is a well-known NP-hard problem. Because of its close relation with the Four Colour Problem, its application in the industry and its computational complexity, Hamiltonian. problem has always been one of the fundamental problems in graph theory.The Hamiltonian and pancyelic problems are associated with many parameters in graphs including minimum degree, degree sum, independent number, connectivity, closure, binding number, the number of edges, the union of neighborhoods, etc. Here we focuse on bipartite graphs, of which the Hamiltonian and bipancyclic problems are two important topics on the cycle structure of bipartite graphs, and will demon-strate the relation of Hamiltonian and bipancyclic problems in balanced bipartite graphs with five basic parameters including degree, minimum degree, connectivity, bipartite binding number and neighborhood.In1989, Tian and Zang [Bipancyclism in Hamiltonian bipartite graphs, Journal of Systems Science and Complexity2(1989),22-31] proved that any Hamiltonian bipartite graph on2n vertices with minimum degree larger than2n/5+2is bi-pancyclic. In Section2, our research goes further to provide that any Hamiltonian bipartite graph on2n vertices with minimum degree at least n/3+5is bipancyclic. The proof of this theorem is more complex, in that various methods are required to prove the existence of even cycle with different lengths. In Subsection2of this section, we prove some basic lemmas on the structure in bipartite graphs, in which Lemma2.2.3gives a sharp bound of co-diameter in2-connected bipartite graphs. This lemma can be regarded as a bipartite graphs’ result lemma given by Bondy and Jackson [Long paths between specified vertices of a block, Ann Discrete Math27(1985),195-200]; in Subsection3, we use nested cycle structures to show the existence of small size even cycle with length from4to2[n/3]; in Subsection4, we use matching connectivity and nested cycle structures to give the proof of existence of middle size even cycle with length from2[n/3] to4[n/3]; in Subsection5, we first design an algorithm to produce a set of segmentally insertable pathes, then employ this algorithm to show the existence of large size even cycle with length from4[n/3]+2to2n; finally in Subsection6, we give the proof of main theorem in this section.In2013, Hu, Law and Zang [An optimal Binding number condition for bipan-cyclism, SIAM J. Discrete Math.27(2013),597-618] proved that any balanced bipartite graph on2n (n≥139) vertices with bipartite binding number B(G)>3/2is bipancyclic. New conditions are introduced in Section2for a2-connected bal-anced bipartite graph to be bipancyclism by combining the minimum degree and bipartite binding number:let0<c<3/2and G be a2-connected balanced bipar-tite graph on2n vertices such that B(G)≥c and δ(G)≥((2-c)/(3-c))n+2/3.hen G is bipancyclic. We use the structure of D3-cycle and the Bipartite Hopping Lemna to complete the proof.In Section4, we prove that any2-connected balanced bipartite graph on2n vertices that satisfies|N(X)|>1/3(n+|X|+1), X(?) Vi is Hamiltonian. This theorem is the bipartite graph form of the conclusion that any2-connected graph on n vertices satisfies that|N(X)|>|(n+|X|-1) for any (?)≠X(?) V(G) and that the minimum degree δ(G)≥(n+2)/3is Hamiltonian, which was given by Woodall.[A sufficient condition for Hamiltonian circuits, J. Combin. Theory Ser. B25(1978),184-186].