Group for Research in Decision Analysis

# Minimum eccentric connectivity index for graphs with fixed order and fixed number of pending vertices

## Gauvain Devillez, Alain Hertz, Hadrien Mélot, and Pierre Hauweele

The eccentric connectivity index of a connected graph $$G$$ is the sum over all vertices $$v$$ of the product $$d_G(v)e_G(v)$$, where $$d_G(v)$$ is the degree of $$v$$ in $$G$$ and $$e_G(v)$$ is the maximum distance between $$v$$ and any other vertex of $$G$$. This index is helpful for the prediction of biological activities of diverse nature, a molecule being modeled as a graph where atoms are represented by vertices and chemical bonds by edges. We characterize those graphs which have the smallest eccentric connectivity index among all connected graphs of a given order $$n$$. Also, given two integers $$n$$ and $$p$$ with $$p\leq n-1$$, we characterize those graphs which have the smallest eccentric connectivity index among all connected graphs of order $$n$$ with $$p$$ pending vertices.

, 11 pages