The Forwarding Indices of Graphs -- a Survey <s> Problems and Trivial Cases <s> A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed. <s> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> Problems and Trivial Cases <s> For a given graph G of order n, a routing R is a set of n(n − 1) elementary paths specified for every ordered pair of vertices in G. The edge forwarding index of a network (G,R), denoted π(G,R) is the maximum number of paths of R going through any edge e of G. The edge forwarding index of G, denoted π(G), is the minimum of π(G,R) taken over all the possible routings R of G. Given n ≤ 15 and Δ ≤ n − 1 we determine πΔ,n, the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. This is known as the edge forwarding index problem. © 1993 by John Wiley & Sons, Inc. <s> BIB002
Problem 4.1 (Chung et al BIB001 ) Given ∆ ≥ 2 and n ≥ 4, determine ξ ∆,n , and exhibit an (n, ∆)-graph G and R of G for which ξ(G, R) = ξ ∆,n . BIB002 ) Given ∆ ≥ 2 and n ≥ 4, determine π ∆,n , and exhibit an (n, ∆)-graph G and R of G for which π(G, R) = π ∆,n .