The Forwarding Index of Antisymmetric Routings

Abstract

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 $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 $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.