Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
A cycle seems like it would be hard to beat, but I have no proof. –  Ross Millikan Mar 31 '12 at 15:09
    
It seems that s(G) = 2W(G) where W is the Wiener Index of a graph mathworld.wolfram.com/WienerIndex.html I am sure this problem was already studied somewhere. –  Jernej May 8 '12 at 16:19
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.