max diameter on regular graphs

I am searching for some time for a relation between the maximum diameter of an undirected k-regular graph and the node-degree k. I couldn't find any result on that. The only useful result is Moon's (1965) bound on the diameter of an undirected graph based on the minimum node-degree of a graph (diamG=3(n-2)/(k+1) - 1, n=#nodes, k=min_node_degree). I like this result but I also consider my graphs to be bi-connected, then the upper bound is n/2 (ring, 2-regular graph), but what for k-regular graphs??

I would appreciate any help on this matter.
Sincerely,
Stefan

Stefan Pascu
Monday, January 19, 2004

This is probably too obvious for words, but I can give you a lower bound on the upper bound :-).

Take a complete graph of order k+1 and remove one edge (say, between v and w). Call this D(k). Now take m copies of D(k) and join them in a ring, attaching neighbouring D(k)s by putting an edge between "v" in one and "w" in its clockwise neighbour. This gives you a biconnected k-regular graph of order m(k+1). Two vertices on opposite sides of the ring have distance something like m+k/2 = n/(k+1)+k/2. So whatever the upper bound on diameter is, it can't be smaller than that.

(By "something like" I mean that the actual value will be something more like m+floor(k/2)-2 or m+ceiling(k/2)-1. I'm too lazy to check the details.)

Together with the result you quoted, this pins the maximum diameter down to within a smallish constant factor, anyway.

Gareth McCaughan
Monday, January 19, 2004

Thanks Gareth,
taking a complete graph is not the best solution, because the distance is minimum (one!), but you gave me a great hint (the ring idea) on how to develop the bound! An n-node k-regular bi-connected graph of max diameter should be a m-node ring connecting (n-m)/2m-node k-regular graphs of max diameter. Proof by induction, on the actual bound. Thanks alot.
S

Stefan Pascu
Monday, January 19, 2004

  Recent Topics

  Fog Creek Home