You might find http://en.wikipedia.org/wiki/Moore_graph relevant — it gives an upper bound for n in terms of degree and diameter (equivalently a lower bound for diameter in terms of degree and n) due to Hoffman and Singleton (1960), that is unfortunately tight only in a small number of cases.
do you want specific numbers or asymptotics ? it’s fairly clear that if the max degree is any constant, the diameter can’t be less than log n, just by an expansion argument.
Exact result depends on whether n is a nice number relative to m. If it is, and the following is an integer:
2 * ( log[base m] ( (n / 2 -1 ) / m ) + 1 )
you have your exact result.
idea – spread the points on a ball and no two points can be more than 1/2 ball away. The diameter is 1/2 the ball. The integer stuff is like trying to cover a ball with different polygons. Triangles, pentigons and hexigons work perfectly. Other polygons will leave weird gaps. Still we can mash our ball to force it to fit since the points do not have to be perfectly symetrical.
We can cover 1/2 the ball with a tree and the other half with an identical tree. Hence the 2 log (n/2). The point we pick as root is special since it can have an extra child. This gives the 2 log ((n/2-1)/m)+1.
Some care must be taken to join the two halves but they can be connected in such a way that any point is indistinguishable from root when the ball is turned (the even distribution).
If the formula comes out to not be an integer my belief is the result is to add one and round but I cannot fully justify this claim.
Under .5 and the extra points can be distributed on 1/2 of the ball adding at most one to the diameter. And .5 or more suggest points must be distributed on both halves of the ball potentially adding 2 to the diameter.
Anyway the problem interest me because I am currently seeking other applications of the diameter. I think it can be used for genome sequencing during the contig scaffolding phase but I am finding other applications and no literature beyond use as a metric.
You might find http://en.wikipedia.org/wiki/Moore_graph relevant — it gives an upper bound for n in terms of degree and diameter (equivalently a lower bound for diameter in terms of degree and n) due to Hoffman and Singleton (1960), that is unfortunately tight only in a small number of cases.
do you want specific numbers or asymptotics ? it’s fairly clear that if the max degree is any constant, the diameter can’t be less than log n, just by an expansion argument.
Suresh: I was hoping for a precise result.
Don: that is a bound, not an exact result.
suresh did give a precise result
let v be number of nodes
let b be max degree
we want min diameter d so
b^d >= v
gives us that
d = log(v,b)
Exact result depends on whether n is a nice number relative to m. If it is, and the following is an integer:
2 * ( log[base m] ( (n / 2 -1 ) / m ) + 1 )
you have your exact result.
idea – spread the points on a ball and no two points can be more than 1/2 ball away. The diameter is 1/2 the ball. The integer stuff is like trying to cover a ball with different polygons. Triangles, pentigons and hexigons work perfectly. Other polygons will leave weird gaps. Still we can mash our ball to force it to fit since the points do not have to be perfectly symetrical.
We can cover 1/2 the ball with a tree and the other half with an identical tree. Hence the 2 log (n/2). The point we pick as root is special since it can have an extra child. This gives the 2 log ((n/2-1)/m)+1.
Some care must be taken to join the two halves but they can be connected in such a way that any point is indistinguishable from root when the ball is turned (the even distribution).
If the formula comes out to not be an integer my belief is the result is to add one and round but I cannot fully justify this claim.
Under .5 and the extra points can be distributed on 1/2 of the ball adding at most one to the diameter. And .5 or more suggest points must be distributed on both halves of the ball potentially adding 2 to the diameter.
Anyway the problem interest me because I am currently seeking other applications of the diameter. I think it can be used for genome sequencing during the contig scaffolding phase but I am finding other applications and no literature beyond use as a metric.