BIPARTITE REGULAR GRAPHS WITH FIXED DIAMETER

For given nonnegative integers k and D, we consider the problem of det ermining n(0)(k, D), the smallest number n for which there exists a k- regular bipartite graph on n vertices with diameter D. We solve the pr oblem for all pairs (k, D) with D not equivalent to 2 (mod 4) and D no t equivalent to 3 (mod 4), for all pairs (k, D) with k even or k prime and D not equivalent to 3 (mod 4), for all pairs with D less than or equal to 9 or k less than or equal to 4, and for a few other pairs. In the remaining cases, we obtain lower and upper bounds for n(0)(k, D). (C) 1995 John Wiley & Sons, Inc.