Let $ d_{G} \left(x,y \right) $ be the length of the shortest path between the vertices $x$ and $y$ in graph $G$ and let $s\left(G\right) = \sum_{x,y \in V \left[G\right]} d_{G} \left(x,y \right)$ . For which undirected, 2-connected n-vertex graphs $G$, value $S(G)$ is the highest?
[Math] Sum of the shortest paths in graph
graph theory
Related Question
- [Math] Finding the shortest and longest average path length in the set of all possible random graphs of a set size and set number of edges
- Graph Theory – Prove That the Graph is Connected
- [Math] Shortest path in a graph with weighted edges and vertices
- Find a node minimizing the sum of shortest distances between a set of other nodes in a graph
Best Answer
It's a cycle, assume there is another graph $G$ which is not cycle and has maximal sum as desired, It has some nodes like $v$ with degree more than two and its degree is minimal (by this condition). $v$'s neighbors are $x_1,x_2,...x_r$ we show them by $N_1(v)$, Also $v$ is on some cycle like $C$, because $G$ is two connected, assume neighbors of $v$ on $C$ are $x_1,x_2$, now if you move $x_2,x_3,..,x_r$ on $C$ and create $C'$ by: $x_1,v,x_2,x_3,...,x_r,...,x_1$ and let other connections be same, newly created graph is two connected, because there is two way between interior vertices of $C'$, also by our construction we didn't affect outer vertices connection, we just replaced an edge with path. Also $G'$ has bigger sum of shortest path, because again we didn't decreases length of a path between vertices of $O = G\backslash (C\cup N_1(v))$, Also we didn't change the length of a paths between vertices in $O$ and $N_1(v) \cup C$, but length of a shortest path between $v$ and $x_3$ increased (by 1). So new graph $G'$ has bigger sum of shortest paths, but this contradict with our assumption. So $G$ can't have a vertex of degree more than 2. and because it's two connected, it's a cycle.