4
$\begingroup$

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?

  • 0
    It seems that s(G) = 2W(G) where W is the Wiener Index of a graph http://mathworld.wolfram.com/WienerIndex.html I am sure this problem was already studied somewhere.2012-05-08

1 Answers 1

4

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.