2
$\begingroup$

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!

  • 0
    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!2012-11-18

1 Answers 1

2

Consider a fixed vertex $v$, and suppose $n-1=kq+r$ with $0 \le r (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.