Structure Of Planar Graphs With Diameter 2 And Related Invariants Of Graphs

The structure characterization and related invariants problem of graphs are two important research topics in graph theory and algebraic combinatorics.The two topics are very important in graph coloring,spectrum characterization and extreme problems and so on.The related problems are widely applied in many scientific fields such as computer science,theoretical physics,chemical graph theory and quantum computing theory.This thesis mainly involves two aspects.On the one hand,we give a structural characterization for non-universal maximal planar graphs with diameter two(abbreviate for MP2-graphs)and study some properties of MP2-graphs,including the number of vertices,pancyclicity.On the other hand,we study some invariants of graphs,including AG index of graphs,Laplacian-energy-like invariant LEL(G),incidence energy IE(G)and Q-generating function and so on.This thesis is divided into four chapters.In chapter 1,we give the introduction,which includes some basic concepts and symbols involved in this thesis,as well as the subject background and research status of related issues.Moreover,the main results of this thesis are briefly summarized.In chapter 2,we study the structure characterization and some properties of planar graphs of diameter 2.Firstly,we describe the structure of non-universal MP2-graphs.Secondly,applying the structural characterization of MP2-graphs,we discuss the pan-cyclicity.We also give the relation between the number of vertices and the maximum degree,which improves the result of Seyffarth in[73].In chapter 3,we study the arithmetic-geometric index of graphs.Firstly,we study the extreme value problem of AG index for MP2-graphs.For MP2-graphs with the minimum degree 4,the extreme graph classes whose AG index reaches the maximum or minimum are obtained.Secondly,on the basis of the previous study of AG index of MP2-graphs,we give some upper and lower bounds of AG index of general graphs and characterize some extreme graphs attaining the bounds.Then,the relationship between AG index and other topological indices of graphs is studied.Finally,the effect of edge deletion on the geometric-arithmetic index GA and AG of graphs is discussed.Furthermore,we give a refinement of Bollobas-Erdos-type theorem obtained in[10].In chapter 4,we investigate the invariants that are closely related to the spectrum of the graph,including Laplacian-energy-like invariant LEL(G),incidence energy IE(G)of graphs,Q-generating function WQ(t),and a new invariant Q-coronal.We present some new upper and lower bounds for Laplacian-energy-like invariant LEL(G)and incidence energy IE(G)of R-graphs and Q-graphs of regular graphs,which improve some results obtained by Pirzada et al.in[67].Some new lower bounds are given on LEL and IE for the line graphs of semi-regular graphs.Finally,it is proved that the Q-generating function wQ(t)can be represented by the Q-polynomial of a graph and its complement graph.We establish the combinatorial expression of Q-coronal of graphs.Furthermore,two new expressions of Q-polynomials about corona graph and edge corona graph mentioned in[11]are given.We also discuss the Q-coronal and Q-generating function of the join of two graphs and the complete multipartite graphs.