Randi(?) Index And Some Other Graph Invariants

Historically, graph theory has a close relation with chemistry. A chemical structure can be conveniently represented by a graph, which is called a chemical graph or a molecular graph. A topological index is a map from the set of chemical graphs to the set of real numbers. Various topological indices are proposed and researched by both theoretical chemists and mathematicians. This thesis consider one popular topological index-Randic index, and study the relations of Randic index and some other graph invariants, such as the chromatic number, the radius, the diameter, the minimum degree, the maximum degree, the order and the size, etc.The Randic index (or the connectivity index) R(G) of a (chemical) graph G vas introduced by the chemist Randic in 1975 as R(G) = (?), where d(u) denotes the degree of a vertex u in G. Randic index has a good correlation with several physicochemical properties of alkanes: boiling points, chromatographic retention times, enthapies of formation, parameters in the An-toine equation for vapor pressure, surface areas, etc. Later, in 1998 Bollobas and Erd(?)s generalized this index by replacing -1/2 with any real numberα, which is called the general Randic index. It has been extensively studied by both theoretical chemists and mathematicians. Many important mathematical properties have been established.In Chapter 1, we introduce the definition and the background of the Randic index, and give the basic notations and terminology related to this thesis. The succeeding five chapters are the main contributions of this thesis:In Chapter 2, we point out the mistakes in the proofs of two theorems in the paper of Hansen and Melot [Variable neighborhood search for extremal graphs 6: Analyzing bounds for the connectivity index, J. Chem. Inf. Comput. Sci. 43(2003), 1-14]. In the two theorems, they studied the relation of the Randic index and the number of pendent vertices of chemical trees. We present the corrected proofs.In Chapter 3, we study the relation between the Randic index R(G) and the minimum degreeδ(G) of graphs and partially solve the open problem proposed by Bollobas and Erd(?)s. In 1988, Shearer proved R(G)≥(?) ifδ(G)≥1. A few months later, Alon improved this bound to (?)-8. In 1998, Bollobas and Erdos proved that R(G)≥(?) ifδ(G)≥1, with equality if and only if G is a star. Bollobas and Erdos asked for the minimum value of the Randic index for graphs with given minimum degree. In 2002, Delorme, Favaron and Rautenbach proposed the conjecture: ifδ(G)≥k, then R(G)≥(?), with equality if and only if G is obtained from a complete bipartite graph K_k,n-k by joining each pair of vertices in the part with k vertices by a new edge. They showed that the conjecture is true for k = 2. We verify this conjecture for k = 3, which can easily lead to the conclusion that the inequality of the conjecture holds for all chemical graphs. Furthermore, we prove that for k≥4, the conjecture is true for any graph of order n≥3/2k³.In the first part of Chapter 4, we give a complete proof to a conjecture, on the relation between the Randic index R(G) and the chromatic numberχ(G) proposed by Caporossi and Hansen: for any connected graph G of order n≥2, R(G)≥(?), the bound is sharp for all n and 2≤χ(G)≤n, where the chromatic number of G is defined as the minimum number of colors that are needed to color the vertices of G properly, i.e., no tow adjacent vertices share a same color. In the second part, we consider the conjecture on the relation between the Randic index R(G) and the radius r(G) proposed by Fajtlowicz: for any connected graph G, R(G)≥r(G)-1, where r(G) denotes the radius of G. From a result on the radius and the minimum degree of graphs given by Erd(?)s et al., we prove that for any connected graph G of order n with minimum degreeδ(G), the conjecture holds forδ(G)≥n/5 and n≥25, furthermore, for any arbitrary real number 0＜ε＜1, ifδ(G)≥εn, the conjecture holds for sufficiently large n. In Chapter 5, we consider the extremal values of the zeroth-order general Randic index of chemical graph G, which is defined as ⁰R_α(G)=(?), whereαis an arbitrary real number. We give the sharp upper and lower bounds of ⁰R_α(G) by using the order n and the size m of G, and characterize the respective extremal graphs.In Chapter 6, we investigate the inverse degree I(G) and the diameter D(G) of graph G, where the inverse degree I(G)=⁰R_-1(G)=(?). Erd(?)s, Pach and Spencer proved that, if G is a connected graph of order n and I(G)≥3, thenwhereμ(G) is the average distance,μ(n,r) = max{μ(G):I(G)≤r}and D(n,r) = max{D(G):I(G)≤r}. Dankelmann et al. improved the upper bound by a factor of 2,We give the sharp upper bounds for trees and unicyclic graphs, which improve the above upper bound by a factor of approximately (?) .