Some Extremal Problems About The Eccentricity Of Graphs

In this thesis, we only consider simple, undirected and connected graphs. The distance dG (u, v) between vertices u and v in a graph G is the length of a shortest path connecting u and v in G, while the eccentricity eccG (u) of a vertex u is the distance to a farthest vertex from u in G. The center C(G) and the periphery P(G) consist of the set of vertices of minimum and maximum eccentricity, respectively, in G. If |C(G)| = |V(G)| -2 , G is called an almost self-centered graph,ASC graph for short. If |P(G)| = |V(G)| -1, G is called an almost-peripheral graph, AP graph for short.In this thesis, we mainly study on the extremal problems of almost self -centered graphs and almost-peripheral graphs. In the first chapter, we briefly recall the basic concepts in graph theory,the related research background and definitions of ASC graph and AP graph. In the second chapter, we determine the 3-ASC index of complete graph, path, cycle and tree of diameter n - 2 (n?10) of order n. At the same time, we prove that ?3 (G) ? {3,4} if G has diameter 2 and other extremal results.In the third chapter, we mainly study on the constructions of ASC graphs and AP graphs, and the upper bound on the embedding index of any graph G. In the fourth chapter, we summarize the results obtained in this thesis and list some related open problems.