Groupe d’études et de recherche en analyse des décisions

G-2001-50

Graphs with Maximum Connectivity Index

, , et

Let G be a graph and dv the degree (= number of first neighbors) of its vertex v. The connectivity index of G is = (du dv)-1/2, with the summation ranging over all pairs of adjacent vertices of G. In a previous paper (Caporossi et al., 1999), 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 exists 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 example are trees with 36 vertices in which one vertex has degree 31.

, 13 pages