ON THE EDGE FORWARDING INDEX PROBLEM FOR SMALL GRAPHS

For a given graph G of order n, a routing R is a set of n(n - 1) eleme ntary paths specified for every ordered pair of vertices in G. The edg e forwarding index of a network (G, R), denoted pi(G, R) is the maximu m number of paths of R going through any edge e of G. The edge forward ing index of G, denoted pi(G), is the minimum of pi(G, R) taken over a ll the possible routings R of G. Given n less-than-or-equal-to 15 and DELTA less-than-or-equal-to n - 1 we determine pi(DELTA,n), the minimu m of pi(G) taken over all graphs G of order n with maximum degree at m ost A. This is known as the edge forwarding index problem.