Graphs with extremal connectivity


Ljiljana Pavlović, Ivan Gutman




Let $G$ be a graph and $\sigma_v$ the degree of its vertex $v$. The connectivity index of $G$ is $\chi=\Sigma(\sigma_u\sigma_v)^{-1/2}$, with the summation ranging over all pairs of adjacent vertices of $G$. We offer a simple proof that (a) among $n$-vertex graphs without isolated vertices, the star has minimal $\chi$-value, and (b) among $n$-vertex graphs, the graphs in which all components are regular of non-zero degree have maximal (mutually equal) $\chi$-values. Both statements (a) and (b) are deduced using the same proof technique, based on linear programming.