Solutions To Three Open Problems On The Randic Index

In this dissertation, we will give complete solutions to three conjectures on the relationship between the Randic index and the minimum degree of connected graphs, the minimum degree of triangle-free graphs, and the girth of connected graphs, respectively.Around the middle of the last century theoretical chemists recognized that useful information on the dependence of various properties of organic substances on molecular structure can be obtained by examining pertinently constructed invariants of the underlying molecular graph. Eventually, graph invariants that are useful for chemical purposes, were named "topological indices" or "molecu-lar structure-descriptors". Their main use is for designing so-called quantitative structure-property relations, QSPR and quantitative structure-activity relations, QSAR. The Randic index which proposed by chemist Randic is one of the out-standing representative among topological indices. For a graph G, its Randic index is defined by where d(u) denotes the degree of a vertex u. At first, Randic was aiming at constructing a mathematical model suitable for describing the extent of branching of organic molecules, especially of the carbon-atom skeleton of alkanes. He then in [71] noticed that there is a good correlation between R and several physico-chemical properties of alkanes:boiling points, chromatographic retention times, enthalpies of formation, parameters in the Antoine equation for vapor pressure, surface areas, etc. In subsequent years countless applications of R were reported, most of them concerned with medicinal and pharmacological issues.The mathematical examination of the Rancic index happened in the second half of the 1990s, when the famous mathematician Erdos began to ask the ex-tremal R-value in some classes of graphs from a mathematical point of view. The works [8,9] of the highly respected Erdos stimulated many other colleagues to study R. In [21] Fajtlowitcz mentioned that Bollobas and Erdos asked for the minimum value on the Randic index for connected graphs with order n and min-imum degreeδ. Especially, in [8] Bollobas and Erdos found the minimum Randic index of connected graphs with order n and minimum degreeδ= 1. In 2002, Delorme, Favaron and Rautenbach [18] solved the problem whenδ= 2, and gave a conjecture, i.e., Conjecture 3.1 about this problem. The cases of Conjecture 3.1 whenδ= 3,δ= [n/2], the number of vertices of the minimum degree nδ≥n-δ(δ≤n/2), have been confirmed by Li and Shi in [56], Pavlovic [66], Pavlovic and Divnic [68], respectively.In [1], however, Aouchiche and Hansen showed that Conjecture 3.1 does not hold in general using the computer system AutoGraphiX and modified it to Conjecture 3.2. In 2007, we checked the cases in [45] whenδequal to n-2, n-3 respectively and modified Conjecture 3.2 to a more precise one, namely, Conjecture 3.3. We show that Conjecture 3.3 is true forδ≥n/2 andδ≤n/2 in Section 3.2 and Section 3.3, respectively. Therefore, this problem, proposed by Bollobas and Erdos, finally being completely solved after more than ten years' effort of mathematical colleagues.In [18], Delorme, Favaron and Rautenbach also gave a best-possible lower bound for the Randic index of a triangle-free graph with given minimum degreeδ. However, Liu, Lu and Tian [52] pointed out a mistake in the proof of this result, and gave a new proof for the case whenδ= 2. It proposed as a conjecture (denoted as "Conjecture 2.1") by Li and Gutman in [46]. In Chapter 2, we will give two different confirmative proofs of Conjecture 2.1.In [2], Aouchiche, Hansen and Zheng proposed Conjecture 4.1 on the rela-tionship between the Randic index and the girth of connected graphs. In 2007, Liu, Zhu, Cai [59] showed that Conjecture 4.1 is true for unicyclic graphs. Wang, Zhu and Liu [81] showed it is true for bicyclic graphs. In Chapter 4, we will prove that Conjecture 4.1 is true in general, solve the conjecture completely.