The forwarding index of communication networks with given connectivity

Answering some questions of Heydemann, Meyer, Opatrny and Sotteau, the authors give upper bounds for the forwarding index of graphs of order n and given connectivity k. They first prove that in a k-connected (respectively k-edge connected) graph with n substantially larger than k, the edge-forwarding index of shortest paths is no more than n²/2-(k-1)n+3(k-1)²/8 (respectively ⌈n²/2⌉-n-2(k-1)²). The authors 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.