# Graph diameter versus maximum node degree

Since I have had amazing luck in the past with questions to the readers of this blog, I have another question.

The diameter of a graph is the longest distance between any two nodes. The degree of a node is the number of edges or links from and to this node.

Intuitively, the higher the node degrees, the denser the graph. If you have n nodes and the maximal degree of the nodes is n-1, then the graph diameter is 1. If you have lesser maximal degrees, then you can get an infinite diameter by producing a disconnected graph.

An interesting question (to me) is:

Given a maximal node degree, and a number of nodes n, what is the smallest possible diameter?

I am sure this is textbook material, but I could not find the answer quickly. Using a hyper-rectangle, I am able to construct a graph having n nodes and log n diameter. Simply start with a 4-node rectangular graph: you have 4 nodes and a diameter of 2. Move to a 8-node cubic graph: you have 8 nodes and a diameter of 3. Generalizing this construction, you have 2d nodes and a diameter of d. Is this the best you can do?

Anyhow. Why do I care about the answer? Because I keep reading that hubs are necessary in graphs to ensure that we have a small diameter. I am trying to quantify this statement. There are about 233 human beings. By my construction above, if everyone knows 33 people, then it is possible to get a diameter of 33. It seems like a relatively large diameter.

An obvious technique to shrink the diameter without using hubs, is to increase the maximal node degree. I am wondering by how much I need to increase the maximal node degree so that I can a 6 degree of separation between any two human beings.

(Yes, I know that social networks are not homogeneous. But stay with me. Assume they were.)

### Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

## 6 thoughts on “Graph diameter versus maximum node degree”

1. D. Eppstein says:

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.

2. 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.

3. 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)

4. 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 )