The Forwarding Indices of Graphs -- a Survey <s> Theorem 2.4 (Heydemann et al <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> Theorem 2.4 (Heydemann et al <s> To measure the efficiency of a routing in network, Chung et al [The forwarding index of communication networks. IEEE Trans. Inform. Theory, 33 (2) (1987), 224-232] proposed the notion of forwarding index and established an upper bound (n − 1)(n − 2) of this parameter for a connected graph of order n. This note improves this bound as (n − 1)(n − 2)− ( 2n− 2−∆ ⌊ 1 + n−1 ∆ ⌋) ⌊ n−1 ∆ ⌋ , where ∆ is the maximum degree of the graph G. This bound is best possible in the sense that there is a graph G attaining it. <s> BIB002
and the equality π(G) = π m (G) = B(G) is true if and only if there exists a minimal routing in G which induces the same load on every edge. The graph that attains this upper bound is a complete bipartite graph K n 2 , n 2 . Recently, Xu et al. BIB002 have showed the star K 1,n−1 is a unique graph that attains the upper bound in (1). Problem 2.5 Note that the upper bound given in (2) can be attained. Give a characterization of graphs whose vertex-or edge-forwarding indices attain the upper bound in BIB001 . Although the two concepts of vertex-and edge-forwarding index are similar, no interesting relationships is known between them except the following trivial inequalities. Theorem 2.6 (Heydemann et al  ) For any connected undirected graph G of order n, maximum degree ∆, minimum degree δ, The inequality in (a) is also valid for minimal routings. No nontrivial graph is found for which the forwarding indices hold one of the above equalities. Thus, it is necessary to further investigate the relationships between π(G) and ξ(G) or between π m (G) and ξ m (G). Problem 2.7 For a graph G and its line graph L(G), investigate the relationships between ξ(G) and π(L(G)) or between ξ m (G) and π m (L(G)).