The forwarding diameter of graphs (Q1270820)

A routing \(R\) in a graph \(G\) is a set of paths \(\{ R_{xy}: x,y \in V(G)\), \(x \not=y\}\) where, for the ordered pair of vertices \((x,y)\), \(R_{xy}\) is a path from \(x\) to \(y\). The load \(\xi (G,R,x)\) of a vertex \(x\) in the routing \(R\) is the number of paths in \(R\) for which \(x\) is an interior vertex. In an earlier paper of Chung et al., \(\xi\) was used to define a measure called the vertex-forwarding index of \(G\). An allied concept is the following: Let \(\mu (G,R) = \max_{x,y \in V(G)} \sum _{z \in V(R_{xy})-\{ x, y \} } \xi (G,R,z)\). The forwarding diameter of \(G\), \(\mu (G)\), is defined as the minimum of \(\mu (G,R)\) over all possible \(R\). The authors employ the theory of queuing networks to explain why \(\mu\) is more suitable than \(\xi\) to handle cases where the object is to minimize the maximum message transmission delay. Bounds for this new index are computed for the cycle, the wheel, the hypercube and the de Bruijn graphs.