So i am reading up on some interesting network topologies for a CS course and what i am reading is $r$-dimensional meshes of tree's.
An $r$-dimensional mesh of trees is formed by adding complete binary tree's to an $N$-sided $r$-dimensional grid where the grid vertices act as the leafs of each binary tree.
Something like this:
This book says this about the graph $G = (V, E)$
$|V| = (r+1)N^r - rN^{r-1}$
$|E| = 2rN^r - 2rN^{r-1}$
And the diameter of this graph (the longest path) is $2rlogN$
How did they come about getting this result? The book does not explain it at all and i do not see how they calculated it.
The book i am reading is: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes is any of you are interested.
EDIT:
I have tried to derive this myself by first finding $|V|$ when $r=2$ which would make it a 2-dimensional mesh of trees.
For this i know there are $2n$ complete binary tree's. Each binary tree have $2^{n-1}-1$ vertices. So this means $2n * 2 ^{n-1} -1$ vetices but we are double counting some because there is a binary tree for every row and column. Therefore we can minus out all the leaves of the column binary trees and they will be accounted in the row binary tree's. So that gives us $n * 2^{n-2}$ vertices to minus from the original.
$2n * (2^{n-1} - 1) - n2^{n-2}$
From this can i just times it by $n$ for 3 dimensions and $n^2$ for 4 dimensions? Then up to $n^{r-2}$ to find the total in $r$-dimensions? Was i calculating this correct for $r=2$? I read somewhere else that when $r=2$ $|V| = 3n^2 - 2n$
Second Edit
Maybe i should use the fact that i know the leafs of each complete binary tree have $n$ vertices which means each binary tree is made out of $n + (n-1)$ vertices.
There are $2n$ complete binary tree's which gives me: $2n(n + (n - 1))$ total vertices which contains a few we counted twice. A total of $n^2$ we counted twice. So
$2n(n + (n-1)) - n^2 = 2n^2 + 2n^2 - 2n - n^2 = 3n^2 - 2n$
That looks right, doesn't it?
So now how would I apply this for 3 dimensions, 4, 5 ect.. all the way to $r$-dimensions?