Research On The Extremal Eccentric Distance Sum Of Graphs With Some Given Parameters

The study for the relationship between the parameters and the structures of graphs is an important research field in the modern graph theory.Let G=(VG, EG) be a simple connected graph. The eccentric distance sum (EDS) of G is defined as ξd(G)=Σv∈VGεG(v)DG(v), where εG(v) is the eccentricity of the vertex v and DG(v)=Σu∈VG dG(u,v) is the sum of all distances from the vertex v. This graph invariant displayed high discriminating power with regard to both biological activity and physical properties. It is used to investigate various physical properties and date sets of analogues. Studies have shown that all results with respect to structure activity and quantitative property studies by using eccentric distance sum are better than the corresponding values obtained by using Wiener’s index. Hence, it is meaningful to study the eccentric distance sum of graphs. The concrete content is in the following:· In Chapter 1, 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, by using deep-going analysis, it fully shows the main work’s necessity and innovation.· In Chapter 2, we give some necessary definitions and lemmas.· In Chapter 3, we give the sharp lower bound on the EDS and characterize the extremal graphs in the class of all connected bipartite graphs with a given matching number q. Moreover, all the extremal graphs having the minimal EDS in the class of odd diameter and vertex connectivity are characterized, respectively.· In Chapter 4, a sharp lower bound on the EDS and the extremal graph in the class of all n-vertex connected triangle-free graphs is determined. Furthermore, the sharp lower bounds on the EDS and the extremal graphs in the class of all n-vertex connected graphs with a given size m and diameter are characterized, respectively. Then we identify a sharp upper bound on the EDS of n-vertex graph with given (even) connectivity, and the extremal graph with maximal EDS are characterized as well.· In Chapter 5, we summarize the main results in this paper and give some prospects for further research in the future.