Menu
Given a connected graph \( G \) with \( n \) vertices, a routing \( R \) is a collection of \( n(n-1) \) paths, one path \( R(x,y) \) for each ordered pair \( x, y \) of vertices. A routing is said to be vertex/edge-antisymmetric if for every pair \( x, y \) of vertices, the paths \( R(x,y) \) and \( R(y,x) \) are internally vertex/edge-disjoint. Compared to other types of routing found in the literature, antisymmetric routing is interesting from a practical point of view because it ensures greater network reliability.
For a given graph \( G \) and routing \( R \), the vertex/edge load of \( G \) with respect to \( R \) is the maximum number of paths passing through any vertex/edge of \( G \). The \emph{vertex/edge-forwarding-index} of a graph is the minimum vertex/edge load taken over all routings. If routing \( R \) is vertex/edge-antisymmetric, we talk about \emph{antisymmetric-indices}.
Several results exist in the literature for the forwarding-indices of graphs. In this paper, we derive upper and lower bounds for the antisymmetric-indices of graphs in terms of their connectivity or minimum degree. These bounds are often the best possible. Whenever this is the case, a network that meets the corresponding bound is described. Several related conjectures are proposed throughout the paper.