What are the simple graphs on $n$ vertices and at most $m$ edges, which have the lowest maximal geodesic betweenness centrality?
To clarify, the maximal geodesic betweenness centrality $B^*$ of a graph $G$ is defined as $B^* = \max_vB(v)$, where $B(v)$ is the geodesic betweenness centrality of node $v$.
Trivially, if $m = {n \choose 2}$, the complete graph will minimize it. What about the intermediate $m$?
From the paper by Guimera et al (2002), it seems to indicate a homogeneous graph structure minimises $B^*$, but is there a exact description of these graphs? And a proof of optimality?