Forwarding indices of k-connected graphs

AbstractFor 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