The Forwarding Indices of Graphs -- a Survey <s> For Cartesian Product Graphs <s> This book provides the most basic problems, concepts, and well-established results from the topological structure and analysis of interconnection networks in the graph-theoretic language. It covers the basic principles and methods of network design, several well-known networks such as hypercubes, de Bruijn digraphs, Kautz digraphs, double loop, and other networks, and the newest parameters to measure performance of fault-tolerant networks such as Menger number, Rabin number, fault-tolerant diameter, wide-diameter, restricted connectivity, and (l,w)-dominating number. Audience: The book is suitable for those readers who are working on or intend to start research in design analysis of the topological structure of interconnection networks, particularly undergraduates and postgraduates specializing in computer science and applied mathematics. <s> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> For Cartesian Product Graphs <s> 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 $\xi(G)$ (the edge-forwarding index $\pi(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\,(\ge 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. <s> BIB002
The cartesian product can preserve many desirable properties of the factor graphs. A number of important graph-theoretic parameters, such as degree, diameter and connectivity, can be easily calculated from the factor graphs. In particular, the cartesian product of vertex-transitive (resp. Cayley) graphs is still a vertex-transitive (resp. Cayley) graph (see Section 2.3 in BIB001 ). Since quasi-Cayley graphs are vertex-transitive, the cartesian product of quasi-Cayley graphs is still a quasi-Cayley graph. Thus, determining the forwarding indices of the cartesian product graphs is of interest. Heydemann et al  obtained the following results first. Theorem 2.14 Let G and G ′ be two connected graphs with order n and n ′ , respectively. Then The inequalities are also valid for minimal routings. Moreover, the equality in (a) holds if both G and G ′ are Cayley digraphs. Recently, Xu et al BIB002 have considered the cartesian product of k graphs and obtained the following results. By Theorem 2.15 and Theorem 2.10, the cartesian product of quasi-Cayley graphs is vertex-optimal and the cartesian product of orbital regular graphs is edge-optimal.