On The Extremal Balaban Index And Szeged Index Of Two Classes Of Graphs

Let G= (V, E) be a connected simple graph. Let dG(u, v) denote the distance between two vertices u and v in G, which is the length of a shortest path between u and v in G. Let DG(u)=Σv∈V(G)dG(u, v), which is the distance sum of vertex u in G. The Balaban index is a distance-based topological invariant of graphs, and it is defined as: where μ= m - n+1, m,n are the number of edges and vertices of G, respectively.The name "Balaban index" was introduced in 1982 by A.T. Balaban, a fa-mous chemist and mathematics chemist. Furthermore, Balaban et al. proposed the concept of the Sum-Balaban index of a connected graph G. It is defined byThese two indices have a good application background in chemistry, and were widely used in QSAR/QSPR modeling. In this thesis, we study the extremal problem of Balaban index and Sum-Balaban index among all bicyclic graphs and provide the tight upper bounds.In 1994, Gutman presented a distance-based topological invariant named as Szeged index, defined by with nv(u)(e)=|Nv(u)(e)|, Nu(e)={w ∈ V(G):dG(u,w)< dG(v,w)}. Randic found the Szeged index does not count the contributions of the vertices at equal distances to the two endpoints of an edge and then proposed the revised Szeged index as follows with n0(e)=|N0(e)|, N0(e)={w ∈ V(G):dG(u,w)= dG(v,w)}. These topological indices introduced above are investigated widely. Knor et al. gave an upper bound for the Balaban index of r-regular graphs on n vertices and a better upper bound for fullerene graphs. They also proposed the following open problem:explore similar bounds for other topological invariants of these graphs. We present the upper and lower bounds of these four invariants for regular graphs.In Chapter 1, we first introduce the basic knowledge of graph theory, the background and the research progress of some topological invariants, then we list an overview of the main results of this thesis.Chapter 2 is devoted to giving a the sharp upper bounds of Balaban in-dex and Sum-Balaban index among all bicyclic graphs, by defining some graph transformations. The graphs attained these bounds are also characterized.In Chapter 3, we consider the open problems proposed by Knor et al, and give the sharp upper bounds of Sum-Balaban index among r-regular graphs with n vertices, and the upper and lower bounds for the (revised) Szeged index of r-regular graphs. At the end of this chapter, the bounds of these indices of some special regular graphs-cubic graphs and fullerene graphs are proposed.In the last chapter, we summarize the primary conclusion of this paper and discuss the future research directions.