Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have $n$ nodes arranged in a circle, and each node is connected to its nearest $k$ neighbors (i.e. $\frac{k}{2}$ on its left, and $\frac{k}{2}$ on its right) with $k$ being even.

The distance between any two nodes is measured by counting the number of edges along the shortest path between them.

My question is, how do I derive the formula (using $n$ and $k$) for the sum of the distances between all possible pairs of nodes in this graph? A breakdown of the derivation would be much appreciated!

share|cite|improve this question
And also: by "number of edges along shortest path" do you mean the number of times the shortest path intersects other edges in the graph? For example if $u,v$ are connected by a single edge in the graph, are you counting how many other segments in the graph cross the edge joining $u,v$ ? – coffeemath Nov 17 '12 at 21:27
@coffeemath, no, I mean the smallest number of edges that will lead from $u$ to $v$. For $u=v$ or any disconnected $u$ and $v$ (i.e. no path between $u$ and $v$), this distance is 0. – skyork Nov 17 '12 at 21:55
Just to make sure I get the definition: For n=11, k=4 (2 on each side) and a fixed vertex v there are four vertices at distance 1, four at distance 2, and two at distance 3 from v? Looks like an interesting problem! – coffeemath Nov 18 '12 at 1:08
up vote 2 down vote accepted

Consider a fixed vertex $v$, and suppose $n-1=kq+r$ with $0 \le r <k$ (that is, $r$ is the remainder on dividing $n-1$ by $k$, and $q$ is the quotient.

Then there are $k$ at distance 1 from $v$, another $k$ at distance 2, and so on, up to a final $k$ at distance $q$ from $v$, and the remaining (if any) $r$ are at distance $q+1$ from $v$. This gives the total contribution from $v$ as $$k(1+2+...+q)+r(q+1)=k\cdot q(q+1)/2 +r(q+1).$$

Since there are $n$ vertices the above must be multiplied by $n$ for the final sum.

EDIT: perhaps this answer has to be divided by 2, since it counts each distance between say $v$ and $w$ twice.

share|cite|improve this answer

Your Answer


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.