I need to know how to compute the sum of the distances between all pairs of “pedal” nodes of the flower graph. And the sum of the distances between all pairs of “stalk” nodes
I know that the average pairwise distance =∑(v1,v2)∈V distance(v1,v2)/(n choose 2), but I dont know how to compute it for this graph
Best Answer
In total, you have $n^2+n$ nodes in your graph. We can first calculate the distances between various pairs of nodes:
Typically we don't calculate the distance from a node to itself when calculating the average distance, so our actual formula is: $$ \bar{d}_G = \frac{1}{\binom{n^2+n}{2}}\sum_{i \neq j \in \{x_1, \dots, x_{n^2}, y_1, \dots, y_n\}} d(i, j) $$ We can divide the above sum into three cases corresponding to the three enumerated dots above. First case, when both vertices are type $x$: $$\bar{d}_1 = \frac{1}{\binom{n^2}{2}}\sum_{i \neq j \in \{x_1, \dots, x_n^2\}}d(i, j) = \frac{1}{\binom{n^2}{2}}\binom{n^2}{2}\cdot 2 = 2$$ The second case, when one vertex is type $x$ and the second vertex is type $y$: $$ \bar{d}_2 = \frac{1}{n^2\cdot n}\sum_{i \in \{x_1, \dots, x_{n^2}\}, j \in \{y_1, \dots, y_n\}} d(i, j) = \frac{1}{n^3}(n^2 \cdot 1 + n^2\cdot 2 + \dots n^2 \cdot n )= \frac{1}{n^3} n^2 \cdot (1 + 2 + \dots + n) = \frac{n+1}{2} $$
Finally, the third case, when both vertices are of $y$ type. Subgraph induced on the vertices of type $y$ is a path on $n$ vertices. Notice that we have $n-1$ pairs of vertices being in distance $1$ from each other, $n-2$ pairs of vertices being in distance $2$ from each other, and so on. So, $$ \bar{d}_3 = \frac{1}{\binom{n}{2}} (1\cdot (n-1) + 2\cdot (n-2) + 3\cdot (n-3) + \dots + (n-1) \cdot 1) = \frac{1}{\binom{n}{2}} \sum_{i=1}^{i=n-1} i\cdot (n-i) = \frac{1}{\binom{n}{2}} \frac{(n-1)n(n+1)}{6} = \frac{n+1}{3} $$
We can now calculate $\bar{d}_G$ as a weighted average of our partial results: $$ \bar{d}_G = \frac{\binom{n^2}{2}\cdot 2 + n^3 \cdot \frac{n+1}{2} + \binom{n}{2}\frac{n+1}{3}}{\binom{n^2+n}{2}} = \frac{9n^2-5n-1}{3(n^2+n-1)} $$