General Randic Index Extremal Problem On The Tree

The theory of topological indices concerned with molecular graphs plays an important role in Combinatorial Chemistry. The topological indices may be used directly as simple numerical descriptors in a comparison with physical (e.g., boiling points of molecules, surface areas) and chemical parameters of molecules. In 1975, Randic proposed an important topological index, called Randic index (also known as the connectivity index), of a molecular graph in his research on molecular structures. This index is well correlated with a variety of physicochemical properties of alkanes, so it attracted much attention of the chemists.In spite of its great popularity among chemists and easily understandable definition, the Randic index was disregarded by mathematicians for a long time. The research on mathematical properties of the Randic index was stimulated by a series of Fajtlowicz's papers describing conjectures obtained with the automated system "Graffiti". The remaining conjectures, may hard to prove or disprove, are submitted to the mathematical community. At that time, it seems that very few mathematicians recognized how difficult and how interesting are the problems encountered in the theory of Randic index.In 1998, Bollobas and Erdos defined the following index (called general Randic index)with summation going over all edges of the graph G andαis an arbitrary real number. This generalization may be viewed as a turning point in the mathematical examination of Randic index. More and more researchers began to study the (general) Randic index for different kinds of graphs (not just for chemical graphs).From a mathematical point of view, the research on the general Randic index in recent years mainly focuses on the following problems: Given a certain class of graphs and some fixed real numberα, how to calculate the maximum or minimum general Randic index? How to characterize the related extremal graphs? The main objective of this thesis is to consider the maximum or minimum general Randic index for trees satisfying certain conditions and characterize the corresponding extremal trees. The thesis has two parts. The first one mainly contributes to the minimum general Randic index for chemical trees, while the second one deals with the maximum or minimum general Randic index for trees.The first part is Chapter 2. We study the minimum general Randic index for chemical trees with a given order and number of pendent vertices. The main techniques we use are induction and linear programming. For the caseα≤-1, we get a lower bound of the minimum general Randic index and we show that our bound is best possible. For other cases, we obtain the minimum general Randic index and characterize the corresponding extremal trees.The second part consists of Chapters 3 and 4. In Chapter 3, we are interested in trees with a given order and diameter. For 0＜α＜1, we give the maximum general Randic index and the related extremal trees. Similarly, we also obtain the minimum general Randic index and the corresponding extremal tree for-1≤α＜0. This implies that a conjecture proposed by Aouchiche, Hansen and Zheng is true for trees.In Chapter 4, we consider trees with a given order and matching number. First, we derive some properties of an extremal tree with the maximum general Randic index forα＞0. We then use these properties to characterize the structure of extremal trees forα＞0. Finally, we obtain the maximum general Randic index for 0＜α≤1 and we show that the corresponding extremal tree is unique.