The Forwarding Indices of Graphs -- a Survey <s> Theorem 4.13 (Heydemann et al <s> Abstract In a given network with n vertices, a routing is defined as a set of n(n — 1) paths, one path connecting each ordered pair of vertices. The load of a vertex is the number of paths going through it. The forwarding index of the network is the minimum of the largest load taken over all routings. We give upper bounds on the forwarding index in k-connected digraphs and in digraphs with half-degrees at least k. Related conjectures are proposed. <s> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> Theorem 4.13 (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
Theorem 4.14 (Heydemann et al  ) If G is a graph of order n and diameter 2 with no end vertex, then π m (G) ≤ 2n − 4. Manoussakis and Tuza BIB001 obtained some upper bounds on the forwarding indies for digraphs subject to degree constraints. Theorem 4.15 Let D be a strongly connected digraph of order n and minimum degree δ. Then Considering the minimum degree δ rather the maximum degree ∆, we can propose an analogy of ξ ∆,n and π ∆,n as follows. Given ∆ and n, let However, the problem determining ξ δ,n and π δ,n is simple. BIB002 ) For any n and δ with n > δ ≥ 1, 5 Difficulty, Methods and Relations to Other Topics