The Forwarding Indices of Graphs -- a Survey <s> Theorem 3.2 (Heydemann et al <s> Abstract For a given connected graph G of order n, a routing R is a set of n(n-1) simple paths one specified for each ordered pair of vertices in G; the pair (G, R) is called a network. The vertex (respectively edge) forwarding index ξ(G, R) (respectively π(G, R)) of a network (G, R) is the maximum number of paths of R passing through any vertex (respectively edge). In this paper we give upper bounds on these parameters, in terms of the number of vertices and the connectivity of the graph, solving some conjectures given in a previous paper. <s> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> Theorem 3.2 (Heydemann et al <s> Abstract Answering some questions of Heydemann, Meyer, Opatrny and Sotteau [4], we give upper bounds for the forwarding index of graphs of order n and given connectivity k. We first prove that in a k-connected (respectively k-connected) graph with n substantially larger than k, the edge-forwarding index of shortest paths is no more than n 2 2 −(k−1)n+ 3(k−1) 2 8 (respectively ⌈ n 2 2 ⌉−n−2(k−1) 2 ) .We next prove that for a k-connected graph the vertex- and edge-forwarding indices are no more than (n−1)⌈ (n−k−1) k ⌉ and n⌈ (n−k−1) k ⌉ , respectively. Related conjectures are proposed. <s> BIB002 </s> The Forwarding Indices of Graphs -- a Survey <s> Theorem 3.2 (Heydemann et al <s> A routing R of a connected graph G of order n is a collection of n(n-1) paths connecting every ordered pair of vertices of G. The vertex-forwarding index ξ(G,R) (resp. the edge-forwarding index π(G,R)) of G with respect to R is defined to be the maximum number of paths of R passing through any vertex (resp. any edge) of G. The vertex-forwarding index ξ(G) (resp. the edge-forwarding index π(G)) of G is defined to be the minimum ξ(G,R) (resp. π(G,R)) over all routings R of G. For a k-regular k-connected graph G, it was shown by Fernandez de la Vega and Manoussakis [Discrete Applied Mathematics, 1989, 23(2): 103-123] that ξ(G)≤(n-1)┌(n-k-1)/k┐ and π(G)≤n┌(n-k-1)/k┐, and conjectured that ξ(G)≤┌(n-k)(n-k-1)/k┐. The upper bounds as ξ(G)≤(n-1)┌(n-k-1)/k┐-(n-k-1) and π(G)≤n┌(n-k-1)/k┐-(n-k) were improved, and the conjecture for k=3 was proved. <s> BIB003
Heydemann et al BIB001 proposed the following research problem. Problem 3.3 Find the best upper bound f (n, k), g(n, k), h(n, k) and s(n, k) such that for any k-connected graph G of order n with k ≥ 2, ξ(G) ≤ f (n, k), ξ m (G) ≤ g(n, k), π(G) ≤ h(n, k) and π m (G) ≤ s(n, k) for n large enough compared to k. Theorem 3.4 (de la Vega and Manoussakis BIB002 ) For any integer k ≥ 1, Recently, Zhou et al. BIB003 have improved the upper bounds of f (n, k) and h(n, k) in Theorem 3.4 as follows. Conjecture 3.6 (de la Vega and Manoussakis BIB002 ) For any positive integer k, Heydemann et al  conjectured that for any λ-edge-connected graph G of order n, π(G) ≤ ⌊ (λ − 1) 2 ⌋. Latter, Heydemann, Meyer, Opatrný and Sotteau BIB001 gave a counterexample and proposed the following conjecture. Conjecture 3.9 for any λ-edge-connected graph G of order n with λ ≥ 3 and n ≥ 3λ + 3, The same problem as the ones in Problem 3.3 can be considered for λ-edge-connected graphs.