Research On Structures And Related Parameters In Graphs

This paper investigate the structures and related parameters in graphs, and it aimed at three aspects. Weakly bipancyclism of bipartite graphs、saturation number of linear forests and the fault-tolerant properties of enhanced hypercubes.The property of Hamiltonian in a graph has been an important and profound research topic in structural graph theory. The origin and development of the prob-lem, which have attracted much attention of graph experts and scholars all over the world, are closely related to the investigation of Four Colour Conjecture. The pan-cyclism and bipancyclism of a graph related to this also become one of important research subject in structural graph theory.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 with In vertices whose minimum degree larger than 2n/5+2 is bipancyclic. In Section 2, our research improved this theorem to provide that if G=(Vi,V2, E) is a bipartite graph satisfied δG[Vi]= min{dG(x):x∪Vi}≥ |V3-i|+4, (?)i= 1,2, then G is a weakly bipancyclic graph of girth 4. As the proof of the existence of even cycle with different lengths require different methods, the proof of this theorem become more complex. In Subsection 1 of this section, we give some basic lemmas on the cycle structure in bipartite graphs. In Subsection 2, we use nested cycle structures to give the proof of the existence of small size even cycle with length from 4 to 2 min {[|V1|/3,[|V2|/3]}+6. In Subsection 3, we use nested cycle structures and matching connectivity to show the existence of middle size even cycle with length from 2 min{[|V1|/3,[|V2|/3]}+8 to 2 min{[|2V1|/3,[|2V2|/3]}.In Subsection 4, we use the way of contradiction and the analyzing of local structure to show the existence of large size even cycle with length from 2 min {[|2V1|/3,[|2V2|/3]} the circumference. Finally in Subsection 5, we give the proof of main theorem.The notion for the saturation number of a graph was introduced by the famous graph expert Erdos et al. in [A problem in graph theory, Amcr. Math. Monthly 71(1964),1107-1110]. In this paper, the authors obtained the saturation number sat(n, Kt) of complete graph Kt, and a characterization of its extremal graph. In 2013,Chen et al.[Saturation Numbers for Linear Forests]proposed a conjecture: for n sufficiently large and t≥3,sat(n,sP3 ∪tP2)=3s+3t-3,and(s+t-1)K3 ∪K-3(s+t-1)∈SAT(n,sP3 ∪tP2).In section 3,we proof this conjecture is true when s=2:Let n≥6t+8,t≥3,then sat(n,2P3 ∪tP2)=3t+3,and SAT(n,2P3 ∪tP2)={(t+1)K3 ∪K-3t-3).The fault-tolerance of a network is an important research content of combina-torial optimization and theoretical computer science,which mainly investigate that whether the network still can work or not when there some number of processors and (or)links fault.Fault-tolerant pancycles,fault-tolerant Hamiltonian properties and fault-tolerant diameter are all important parameters to measure the fault-tolerance of a network.In 2003,Fu[Fault-tolerant cycles embedding in the hypercube,Paral-lel Computing 29(6)(2003),821-832]showed that a fault-free cycle of length at least 2n-2|Fv| can be embedded on Qn with |Fv|≤2n-4,where |Fv| denote the number of faulty vertices. In section 4,we extend the couclusion to enhanced hypercube: enhanced hypercube Qn,k with |Fv|=2n-3 faulty vertices contains a fault-free cycle of length 2n-2|Fv|.