Graph connectivity and Wiener index


I. Gutman, S. Zhang


The graphs with a given number $n$ of vertices and given (vertex or edge) connectivity $k$ , having minimum Wiener index are determined. In both cases this is $K_k+(K_1 \cup K_{n-k-1})$ , the graph obtained by connecting all vertices of the complete graph $K_k$ with all vertices of the graph whose two components are $K_{n-k-1}$ and $K_1$ .