Forwarding indices of Cartesian product graphs

Abstract. For a given connected graph G of order n, a routing R is a set of n(n − 1) elementary paths specified for every ordered pair of vertices in G. The vertex-forwarding index ξ(G) (the edge-forwarding index π(G)) of G is the maximum number of paths of R passing through any vertex (resp. edge) in G. In this paper we consider the vertex- and the edge- forwarding indices of the cartesian product of k ( ≥ 2) graphs. As applications of our results, we determine the vertex- and the edge- forwarding indices of some well-known graphs, such as the n-dimensional generalized hypercube, the undirected toroidal graph, the directed toroidal graph and the cartesian product of the Petersen graphs. 1