The Forwarding Indices of Graphs -- a Survey <s> Results on <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> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> Results on <s> For a given graph G of order n,a routing R is a set of n(n-1) elementary paths such that every ordered pair of vertices in G are connected by a path in the set. The edge-forwarding index of G with respect to a given routing R,denoted by π(G,R),is the maximum number of paths in R passing through any edge e of G.The edge-forwarding index π(G) of G is the minimum of π(G,R) taken over all possible routings R of G.The parameter π_ Δ,n is the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. We determine all values of π_ n-2p,n for n≥ 4p+1 but n4p+(1/3)(2p-1)-1,6p for any p≥1. <s> BIB002
Similar to Theorem 4.5, Bouabdallah and Sotteau BIB001 obtained the following result on π ∆, n Theorem 4.7 For any n and ∆ ≥ 3, (a) π ∆, n ≥ ⌈ n is ∆-regular and diameter 2 and G has a minimal routing for which the load of all edges is the same; (c) π ∆, n ≥ ⌈ 4n−2) ∆ ⌉ − 2 if n and ∆ are odd; (d) π ∆, n ≤ π ∆ ′ , n for any n and ∆ ′ ≤ n − 1 with ∆ ′ < ∆. Problem 4.3 was solved for n ≤ 15 by Bouabdallah and Sotteau BIB001 , who also obtained π n−2,n = 3 for any n ≥ 6, n = 7 and π n−2,n = 4 for any n = 4, 5, 7. Recently, Xu et al  have determined π n−2p−1, n = 8 if 3p + ⌈ 1 3 p⌉ + 1 ≤ n ≤ 3p + ⌈ 3 5 p⌉ and ≥ 2. The authors in the two BIB001 and  have completely determined π n−2p−1,n for n ≥ 4p and p ≥ 1 except a little gap. p⌉ + 1 ≤ n ≤ 6p ; 6, if 4p + 1 ≤ n ≤ 4p + ⌈ 2 3 p⌉. Note the value of π n−2p−1, n has not been determined for 4p + ⌈ 2 3 p⌉ + 1 ≤ n ≤ 4p + 2⌈ 1 3 p⌉. However, these two numbers are different only when p = 3k + 1. Thus, we proposed the following conjecture. p⌉ + 1 ≤ n ≤ 4p + 2⌈ 1 3 p⌉. BIB002 ) For any p ≥ 1, we have