Research On The Structure And Toplogical Parameters In Graphs

This thesis does research on the structure and Topological parameters in graphs. The main content of this thesis is as follows.In the first section, we give some definitions and notations that we needed in this paper. After that, we introduce the background and significance of the research, including the development of a representative at home and abroad regarding this aspect. Based on this research background and profound discussion on the status quo, it fully shows the main work’s necessity and innovation.In the following four sections, we will do research on the structure and some important Topological parameters in graphs, respectively.A broom is a tree obtained from a star by subdividing one edge of the star an arbitrary number of times, which has only one branch vertex. In [G. Chen, M. Ferrara, Z. Hu, M. Jacobson and H. Liu, Degree conditions for spanning brooms, submitted.] Chen et al. posed the conjecture that if G is a connected graph of order n≥3with σ3(G)≥n-2, then G contains a spanning broom. In the second section, we prove that this conjecture is true if the order of graph G is large enough, which solves the problem posed by Flandrin et al. Furthermore, we also prove that if G is a2-connected graph of order n≥50and σ3(G)≥n-2, then either G has a hamiltonian path or G has a spanning jellyfish.A graph G of order n is called a bicyclic graph if G is connected and its number of edges is n+1. He, Shao and He [C. He, J. Shao, J. He, On the Laplacian spectral radius of bicyclic graphs, Discrete Math.308(2008)5981-5995] determined the first four largest Laplacian spectral radii together with the corresponding graphs among the bicyclic graphs of order n. In the third section, we extend this ordering by determined the fifth to eighth largest Laplacian spectral radii together with the corresponding graphs among the bicyclic graphs of order n.Given an n-vertex graph G, the matrix Ω(G)=(In+L(G))-1=(wij) is called the doubly stochastic graph matrix of G, where In is the n x n identity matrix and L(G) is the Laplacian matrix of G. Let ω(G) be the smallest element of Ω(G) Zhang and Wu [X.D. Zhang, J.X. Wu, Doubly stochastic matrices of trees, Appl. Math. Lett.18(2005)339-343] determined the tree T with the minimum ω(T) among the set of n-vertex trees. In the fourth section, as a continuance of it, we determine the first [n-1/2] trees T1,T2,..., T[n-1/2] among the set of n-vertex trees such that w(T1)<ω(T2)<…<ω(T[n-1/2])≤ω(T[n-1/2])<ω(T),where Tt is obtained by attaching a pendant vertex to Vi of path Pn-1=v1v2…vi…vn-1and T∈(?)n\{T1, T2,…,[n-1/2]}, where (?)n is the set of all n-vertex trees.For a graph, the first Zagrob index M1is equal to the sum of squares of its vertex degrees, and the second Zagreb index M2is equal to the sum of products of degrees of pairs of adjacent vertices. A connected graph G is a cactus if any two of its cycles have at most one common vertex. In the fifth section, we determine sharp bounds for the first and the second Zagreb indices of cacti with k pendant vertices. As a consequence, we determine the n-vertex cacti with maximal Zagreb indices. Moreover, we also determine the cactus with a perfect matching having maximal Zagreb indices.