Minimum Eccentric Connectivity Index for Graphs With Fixed Order and Fixed Number of Pendant


Gauvain Devillez, Alain Hertz, Hadrien Mélot, 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$. We characterize, with a new elegant proof, those graphs which have the smallest eccentric connectivity index among all connected graphs of a given order $n$. Then, given two integers $n$ and $p$ with $p \le n-1$, we characterize those graphs which have the smallest eccentric connectivity index among all connected graphs of order $n$ with $p$ pendant vertices.