On forwarding indices of networks (Q1823868)

The authors define a network as an undirected graph and a set of simple paths connecting every ordered pair of vertices. They define the edge- forwarding index of a network as the maximum number of paths passing through any network edge. This concept is similar to that introduced by \textit{F. R. K. Chung, E. G. Coffman, M. I. Reiman} and \textit{B. E.Simon} [IEEE Trans. Inf. Theory 33, 224-232 (1987; Zbl 0626.94019)] who defined the node-forwarding index. Lower and upper bounds for both forwarding indices are presented in the general case, and are specified for trees, bipartite graphs, p-cubes, de Bruijn graphs, line graphs, Peterson graphs, and some others. The computational complexity of finding the exact values of the indices seems to be an open problem.