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
    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$ ?2012-11-17
  • 0
    @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.2012-11-17
  • 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.