Graphs with maximum connectivity index
Let G be a graph and dv the degree (=number of first neighbors) of its vertex v. The connectivity index of G is ?=?(dudv)?1/2, with the summation ranging over all pairs of adjacent vertices of G. In a previous paper (Comput. Chem. 23 (1999) 469), by applying a heuristic combinatorial optimization algorithm, the structure of chemical trees possessing extremal (maximum and minimum) values of ? was determined. It was demonstrated that the path Pn is the n-vertex tree with maximum ?-value. We now offer an alternative approach to finding (molecular) graphs with maximum ?, from which the extremality of Pn follows as a special case. By eliminating a flaw in the earlier proof, we demonstrate that there exist cases when ? does not provide a correct measure of branching: we find pairs of trees T,T?, such that T is more branched than T?, but ?(T)>?(T?). The smallest such examples are trees with 36 vertices in which one vertex has degree 31.
connectivity index branching randi? index extremal graphs molecular graph chemical graph theory