The least balanced graphs and trees

Abstract

Given a connected graph, the principal eigenvector of the adjacency matrix (often called the Perron vector) can be used to assign positive weights to the vertices. A natural way to measure the homogeneousness of this vector is by considering the ratio of its ${\ell }^1$ and ${\ell }^2$ norms. It is easy to see that the most balanced graphs in this sense (i.e., the ones with the largest ratio) are the regular graphs. What can we say about the least balanced (or most centralized) graphs with the smallest ratio? It was conjectured by Rücker, Rücker and Gutman that, for any given $n\ge 6$, among $n$-vertex connected graphs the smallest ratio is achieved by the complete graph $K_4$ with a single path $P_{n-4}$ attached to one of its vertices. In this paper we confirm this conjecture. We also verify the analogous conjecture for trees: for any given $n\ge 8$, among $n$-vertex trees the smallest ratio is achieved by the star graph $S_5$ with a path $P_{n-5}$ attached to its central vertex.