OPTIMAL ROUTINGS IN COMMUNICATION-NETWORKS WITH LINEARLY BOUNDED FORWARDING INDEX

In a given graph with n vertices, a routing is defined as a set of n(n - 1) routes, one route connecting each ordered pair of vertices. The load of a vertex is the number of routes going through it. The forward ing index of the graph is the minimum of the largest load taken over a ll routings. We construct undirected graphs with a high degree of symm etry and specified diameter, in which the load of every vertex is at m ost constant times the number of vertices. This gives a partial soluti on to a problem of Chung et al. (C) 1996 John Wiley & Sons, Inc.