
max diameter on regular graphs
I am searching for some time for a relation between the maximum diameter of an undirected kregular graph and the nodedegree 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 nodedegree of a graph (diamG=3(n2)/(k+1)  1, n=#nodes, k=min_node_degree). I like this result but I also consider my graphs to be biconnected, then the upper bound is n/2 (ring, 2regular graph), but what for kregular 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 kregular 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 nnode kregular biconnected graph of max diameter should be a mnode ring connecting (nm)/2mnode kregular 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
