The Forwarding Indices of Graphs -- a Survey
---
paper_title: The forwarding index of communication networks

paper_content:

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.
---
paper_title: The forwarding index of communication networks

paper_content:

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.
---
paper_title: Forwarding indices of consistent routings and their complexity

paper_content:

For a given connected graph G of order n, a routing R is a set of n(n - 1) simple paths R(x, y) specified for every ordered pair (x, y) of vertices in G. A routing R is consistent if for every vertex z on R(x, y) the paths R(x, z) and R(z, y) are induced by R(x, y). A network is defined by an ordered pair (G, R), where G is a connected graph and R is a routing of G. The vertex-forwarding index ζ(G, R) of a network (G, R) is the maximum number of paths of R passing through any vertex of G. The minimum of ζ(G, R) over all possible routings of a connected graph G is denoted by ζ(G). Similarly, the notion of the edge-forwarding index of a network can be defined. In this paper, we prove that, in general, the vertex-forwarding index cannot be obtained by taking the minimum of ζ(G, R) over all possible consistent routings of G. However, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of ζ(G) is NP-complete for graphs of diameter at least 4 and is polynomial for graphs of diameter 2. Similar problems are studied for the edge-forwarding index. © 1994 John Wiley & Sons, Inc.
---
paper_title: Forwarding indices of consistent routings and their complexity

paper_content:

For a given connected graph G of order n, a routing R is a set of n(n - 1) simple paths R(x, y) specified for every ordered pair (x, y) of vertices in G. A routing R is consistent if for every vertex z on R(x, y) the paths R(x, z) and R(z, y) are induced by R(x, y). A network is defined by an ordered pair (G, R), where G is a connected graph and R is a routing of G. The vertex-forwarding index ζ(G, R) of a network (G, R) is the maximum number of paths of R passing through any vertex of G. The minimum of ζ(G, R) over all possible routings of a connected graph G is denoted by ζ(G). Similarly, the notion of the edge-forwarding index of a network can be defined. In this paper, we prove that, in general, the vertex-forwarding index cannot be obtained by taking the minimum of ζ(G, R) over all possible consistent routings of G. However, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of ζ(G) is NP-complete for graphs of diameter at least 4 and is polynomial for graphs of diameter 2. Similar problems are studied for the edge-forwarding index. © 1994 John Wiley & Sons, Inc.
---
paper_title: The forwarding index of communication networks

paper_content:

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.
---
paper_title: A New Upper Bound On Forwarding Index of Graphs ∗

paper_content:

To measure the efficiency of a routing in network, Chung et al [The forwarding index of communication networks. IEEE Trans. Inform. Theory, 33 (2) (1987), 224-232] proposed the notion of forwarding index and established an upper bound (n − 1)(n − 2) of this parameter for a connected graph of order n. This note improves this bound as (n − 1)(n − 2)− ( 2n− 2−∆ ⌊ 1 + n−1 ∆ ⌋) ⌊ n−1 ∆ ⌋ , where ∆ is the maximum degree of the graph G. This bound is best possible in the sense that there is a graph G attaining it.
---
paper_title: On the edge forwarding index problem for small graphs

paper_content:

For a given 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 edge forwarding index of a network (G,R), denoted π(G,R) is the maximum number of paths of R going through any edge e of G. The edge forwarding index of G, denoted π(G), is the minimum of π(G,R) taken over all the possible routings R of G. Given n ≤ 15 and Δ ≤ n − 1 we determine πΔ,n, the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. This is known as the edge forwarding index problem. © 1993 by John Wiley & Sons, Inc.
---
paper_title: Forwarding indices of consistent routings and their complexity

paper_content:

For a given connected graph G of order n, a routing R is a set of n(n - 1) simple paths R(x, y) specified for every ordered pair (x, y) of vertices in G. A routing R is consistent if for every vertex z on R(x, y) the paths R(x, z) and R(z, y) are induced by R(x, y). A network is defined by an ordered pair (G, R), where G is a connected graph and R is a routing of G. The vertex-forwarding index ζ(G, R) of a network (G, R) is the maximum number of paths of R passing through any vertex of G. The minimum of ζ(G, R) over all possible routings of a connected graph G is denoted by ζ(G). Similarly, the notion of the edge-forwarding index of a network can be defined. In this paper, we prove that, in general, the vertex-forwarding index cannot be obtained by taking the minimum of ζ(G, R) over all possible consistent routings of G. However, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of ζ(G) is NP-complete for graphs of diameter at least 4 and is polynomial for graphs of diameter 2. Similar problems are studied for the edge-forwarding index. © 1994 John Wiley & Sons, Inc.
---
paper_title: Cayley Graphs and Interconnection Networks

paper_content:

Due to recent developments of parallel and distributed computing, the design and analysis of various interconnection networks has been a main topic of research for the past few years and is still stimulated by the new technologies of communication networks such as optic fibers. There are many advantages in using Cayley (di)graphs as models for interconnection networks. This work first surveys some classes of Cayley graphs which are well studied as models of interconnection networks. Results and problems related to routings in networks are then presented, with emphasis on loads of nodes and links in routings.
---
paper_title: Forwarding indices of consistent routings and their complexity

paper_content:

For a given connected graph G of order n, a routing R is a set of n(n - 1) simple paths R(x, y) specified for every ordered pair (x, y) of vertices in G. A routing R is consistent if for every vertex z on R(x, y) the paths R(x, z) and R(z, y) are induced by R(x, y). A network is defined by an ordered pair (G, R), where G is a connected graph and R is a routing of G. The vertex-forwarding index ζ(G, R) of a network (G, R) is the maximum number of paths of R passing through any vertex of G. The minimum of ζ(G, R) over all possible routings of a connected graph G is denoted by ζ(G). Similarly, the notion of the edge-forwarding index of a network can be defined. In this paper, we prove that, in general, the vertex-forwarding index cannot be obtained by taking the minimum of ζ(G, R) over all possible consistent routings of G. However, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of ζ(G) is NP-complete for graphs of diameter at least 4 and is polynomial for graphs of diameter 2. Similar problems are studied for the edge-forwarding index. © 1994 John Wiley & Sons, Inc.
---
paper_title: The edge-forwarding index of orbital regular graphs

paper_content:

Abstract We define a graph as orbital regular if there is a subgroup of its automorphism group that acts regularly on the set of edges of the graph as well as on all its orbits of ordered pairs of distinct vertices of the graph. For these graphs there is an explicit formula for the edge-forwarding index, an important traffic parameter for routing in interconnection networks. Using the arithmetic properties of finite fields we construct infinite families of graphs with low edge-forwarding properties. In particular, the edge-forwarding index of Paley graphs is determined. A connection with the Waring problem over finite fields and the coset weight enumeration of certain cyclic codes is established.
---
paper_title: Edge-forwarding index of star graphs and other Cayley graphs

paper_content:

We present a technique for building, in some Cayley graphs, a routing for which the load of every edge is almost the same. This technique enables us to find the edge-forwarding index of star graphs and complete-transposition graphs.
---
paper_title: On quasi-Cayley graphs

paper_content:

Abstract We introduce the concept of quasi-Cayley graphs, a class of vertex-transitive graphs which contains Cayley graphs, and study some of their properties. By finding vertex-transitive graphs which are not quasi-Cayley graphs we give a negative answer to a question by Fuller and Krishnamurthy on the quasi-group representation of a vertex-transitive graph.
---
paper_title: Topological Structure and Analysis of Interconnection Networks

paper_content:

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.
---
paper_title: FORWARDING INDICES OF CARTESIAN PRODUCT GRAPHS

paper_content:

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.
---
paper_title: Forwarding indices of k-connected graphs

paper_content:

Abstract For a given connected graph G of order n, a routing R is a set of n(n-1) simple paths one specified for each ordered pair of vertices in G; the pair (G, R) is called a network. The vertex (respectively edge) forwarding index ξ(G, R) (respectively π(G, R)) of a network (G, R) is the maximum number of paths of R passing through any vertex (respectively edge). In this paper we give upper bounds on these parameters, in terms of the number of vertices and the connectivity of the graph, solving some conjectures given in a previous paper.
---
paper_title: Forwarding indices of k-connected graphs

paper_content:

Abstract For a given connected graph G of order n, a routing R is a set of n(n-1) simple paths one specified for each ordered pair of vertices in G; the pair (G, R) is called a network. The vertex (respectively edge) forwarding index ξ(G, R) (respectively π(G, R)) of a network (G, R) is the maximum number of paths of R passing through any vertex (respectively edge). In this paper we give upper bounds on these parameters, in terms of the number of vertices and the connectivity of the graph, solving some conjectures given in a previous paper.
---
paper_title: Forwarding indices of 3-connected and 3-regular graphs

paper_content:

A routing R of a connected graph G of order n is a collection of n(n-1) paths connecting every ordered pair of vertices of G. The vertex-forwarding index ξ(G,R) (resp. the edge-forwarding index π(G,R)) of G with respect to R is defined to be the maximum number of paths of R passing through any vertex (resp. any edge) of G. The vertex-forwarding index ξ(G) (resp. the edge-forwarding index π(G)) of G is defined to be the minimum ξ(G,R) (resp. π(G,R)) over all routings R of G. For a k-regular k-connected graph G, it was shown by Fernandez de la Vega and Manoussakis [Discrete Applied Mathematics, 1989, 23(2): 103-123] that ξ(G)≤(n-1)┌(n-k-1)/k┐ and π(G)≤n┌(n-k-1)/k┐, and conjectured that ξ(G)≤┌(n-k)(n-k-1)/k┐. The upper bounds as ξ(G)≤(n-1)┌(n-k-1)/k┐-(n-k-1) and π(G)≤n┌(n-k-1)/k┐-(n-k) were improved, and the conjecture for k=3 was proved.
---
paper_title: The forwarding index of communication networks with given connectivity

paper_content:

Abstract Answering some questions of Heydemann, Meyer, Opatrny and Sotteau [4], we give upper bounds for the forwarding index of graphs of order n and given connectivity k. We first prove that in a k-connected (respectively k-connected) graph with n substantially larger than k, the edge-forwarding index of shortest paths is no more than n 2 2 −(k−1)n+ 3(k−1) 2 8 (respectively ⌈ n 2 2 ⌉−n−2(k−1) 2 ) .We next prove that for a k-connected graph the vertex- and edge-forwarding indices are no more than (n−1)⌈ (n−k−1) k ⌉ and n⌈ (n−k−1) k ⌉ , respectively. Related conjectures are proposed.
---
paper_title: The forwarding index of communication networks with given connectivity

paper_content:

Abstract Answering some questions of Heydemann, Meyer, Opatrny and Sotteau [4], we give upper bounds for the forwarding index of graphs of order n and given connectivity k. We first prove that in a k-connected (respectively k-connected) graph with n substantially larger than k, the edge-forwarding index of shortest paths is no more than n 2 2 −(k−1)n+ 3(k−1) 2 8 (respectively ⌈ n 2 2 ⌉−n−2(k−1) 2 ) .We next prove that for a k-connected graph the vertex- and edge-forwarding indices are no more than (n−1)⌈ (n−k−1) k ⌉ and n⌈ (n−k−1) k ⌉ , respectively. Related conjectures are proposed.
---
paper_title: The forwarding index of directed networks

paper_content:

Abstract In a given network with n vertices, a routing is defined as a set of n(n — 1) paths, one path connecting each ordered pair of vertices. The load of a vertex is the number of paths going through it. The forwarding index of the network is the minimum of the largest load taken over all routings. We give upper bounds on the forwarding index in k-connected digraphs and in digraphs with half-degrees at least k. Related conjectures are proposed.
---
paper_title: On the edge forwarding index problem for small graphs

paper_content:

For a given 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 edge forwarding index of a network (G,R), denoted π(G,R) is the maximum number of paths of R going through any edge e of G. The edge forwarding index of G, denoted π(G), is the minimum of π(G,R) taken over all the possible routings R of G. Given n ≤ 15 and Δ ≤ n − 1 we determine πΔ,n, the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. This is known as the edge forwarding index problem. © 1993 by John Wiley & Sons, Inc.
---
paper_title: The forwarding index of communication networks

paper_content:

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.
---
paper_title: On the edge forwarding index problem for small graphs

paper_content:

For a given 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 edge forwarding index of a network (G,R), denoted π(G,R) is the maximum number of paths of R going through any edge e of G. The edge forwarding index of G, denoted π(G), is the minimum of π(G,R) taken over all the possible routings R of G. Given n ≤ 15 and Δ ≤ n − 1 we determine πΔ,n, the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. This is known as the edge forwarding index problem. © 1993 by John Wiley & Sons, Inc.
---
paper_title: The forwarding index of communication networks

paper_content:

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.
---
paper_title: The forwarding index of communication networks

paper_content:

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.
---
paper_title: On Edge-Forwarding Index of Graphs with Degree Restriction

paper_content:

For a given graph G of order n,a routing R is a set of n(n-1) elementary paths such that every ordered pair of vertices in G are connected by a path in the set. The edge-forwarding index of G with respect to a given routing R,denoted by π(G,R),is the maximum number of paths in R passing through any edge e of G.The edge-forwarding index π(G) of G is the minimum of π(G,R) taken over all possible routings R of G.The parameter π_ Δ,n is the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. We determine all values of π_ n-2p,n for n≥ 4p+1 but n4p+(1/3)(2p-1)-1,6p for any p≥1.
---
paper_title: On the edge forwarding index problem for small graphs

paper_content:

For a given 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 edge forwarding index of a network (G,R), denoted π(G,R) is the maximum number of paths of R going through any edge e of G. The edge forwarding index of G, denoted π(G), is the minimum of π(G,R) taken over all the possible routings R of G. Given n ≤ 15 and Δ ≤ n − 1 we determine πΔ,n, the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. This is known as the edge forwarding index problem. © 1993 by John Wiley & Sons, Inc.
---
paper_title: A New Upper Bound On Forwarding Index of Graphs ∗

paper_content:

To measure the efficiency of a routing in network, Chung et al [The forwarding index of communication networks. IEEE Trans. Inform. Theory, 33 (2) (1987), 224-232] proposed the notion of forwarding index and established an upper bound (n − 1)(n − 2) of this parameter for a connected graph of order n. This note improves this bound as (n − 1)(n − 2)− ( 2n− 2−∆ ⌊ 1 + n−1 ∆ ⌋) ⌊ n−1 ∆ ⌋ , where ∆ is the maximum degree of the graph G. This bound is best possible in the sense that there is a graph G attaining it.
---
paper_title: A New Upper Bound On Forwarding Index of Graphs ∗

paper_content:

To measure the efficiency of a routing in network, Chung et al [The forwarding index of communication networks. IEEE Trans. Inform. Theory, 33 (2) (1987), 224-232] proposed the notion of forwarding index and established an upper bound (n − 1)(n − 2) of this parameter for a connected graph of order n. This note improves this bound as (n − 1)(n − 2)− ( 2n− 2−∆ ⌊ 1 + n−1 ∆ ⌋) ⌊ n−1 ∆ ⌋ , where ∆ is the maximum degree of the graph G. This bound is best possible in the sense that there is a graph G attaining it.
---
paper_title: The forwarding index of directed networks

paper_content:

Abstract In a given network with n vertices, a routing is defined as a set of n(n — 1) paths, one path connecting each ordered pair of vertices. The load of a vertex is the number of paths going through it. The forwarding index of the network is the minimum of the largest load taken over all routings. We give upper bounds on the forwarding index in k-connected digraphs and in digraphs with half-degrees at least k. Related conjectures are proposed.
---
paper_title: Edge congestion and topological properties of crossed cubes

paper_content:

An n-dimensional crossed cube, CQ/sub n/, is a variation of hypercubes. In this paper, we give a new shortest path routing algorithm based on a new distance measure defined herein. In comparison with Efe's algorithm, which generates one shortest path in O(n/sup 2/) time, our algorithm can generate more shortest paths in O(n) time. Based on a given shortest path routing algorithm, we consider a new performance measure of interconnection networks called edge congestion. Using our shortest path routing algorithm and assuming that message exchange between all pairs of vertices is equally probable, we show that the edge congestion of crossed cubes is the same as that of hypercubes. Using the result of edge congestion, we can show that the bisection width of crossed cubes is 2/sup n-1/. We also prove that wide diameter and fault diameter are [n/2]+2. Furthermore, we study embedding of cycles in cross cubes and construct more types than previous work of cycles of length at least four.
---
paper_title: On the edge forwarding index problem for small graphs

paper_content:

For a given 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 edge forwarding index of a network (G,R), denoted π(G,R) is the maximum number of paths of R going through any edge e of G. The edge forwarding index of G, denoted π(G), is the minimum of π(G,R) taken over all the possible routings R of G. Given n ≤ 15 and Δ ≤ n − 1 we determine πΔ,n, the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. This is known as the edge forwarding index problem. © 1993 by John Wiley & Sons, Inc.
---
paper_title: Interconnection Networks Based on a Generalization of Cube-Connected Cycles

paper_content:

A generalization of the cube-connected cycles of Preparata and Vuillemin is described which retains the symmetry of these architectures while allowing for constructions of greater density and of arbitrary degree. These constructions are of a type known as Cayley graphs, and their analysis is greatly facilitated by the applicability of methods from abstract algebra.
---
paper_title: The forwarding indices of augmented cubes ✩

paper_content:

For a given connected graph G of order n, a routing R in G is a set of n(n-1) elementary paths specified for every ordered pair of vertices in G. The vertex (resp. edge) forwarding index of G is the maximum number of paths in R passing through any vertex (resp. edge) in G. Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2002) 71-84] proposed a variant of the hypercube Q"n, called the augmented cube AQ"n and presented a minimal routing algorithm. This paper determines the vertex and the edge forwarding indices of AQ"n as 2^n9+(-1)^n^+^19+n2^n3-2^n+1 and 2^n^-^1, respectively, which shows that the above algorithm is optimal in view of maximizing the network capacity.
---
paper_title: Forwarding index of cube-connected cycles

paper_content:

For a given connected graph G of order v, a routing R in G is a set of v(v-1) elementary paths specified for every ordered pair of vertices in G. The vertex (resp. edge) forwarding index of G is the maximum number of paths in R passing through any vertex (resp. edge) in G. Shahrokhi and Szekely [F. Shahrokhi, L.A. Szekely, Constructing integral flows in symmetric networks with application to edge forwarding index problem, Discrete Applied Mathematics 108 (2001) 175-191] obtained an asymptotic formula for the edge forwarding index of n-dimensional cube-connected cycle CCC"n as 54n^22^n(1-o(1)). This paper determines the vertex forwarding index of CCC"n as 74n^22^n(1-o(1)) asymptotically.
---
paper_title: Interconnection Networks Based on a Generalization of Cube-Connected Cycles

paper_content:

A generalization of the cube-connected cycles of Preparata and Vuillemin is described which retains the symmetry of these architectures while allowing for constructions of greater density and of arbitrary degree. These constructions are of a type known as Cayley graphs, and their analysis is greatly facilitated by the applicability of methods from abstract algebra.
---
paper_title: Constructing Integral Uniform Flows in Symmetric Networks With Application to the Edge-Forwarding Index Problem

paper_content:

Abstract We study the integral uniform (multicommodity) flow problem in a graph G and construct a fractional solution whose properties are invariant under the action of a group of automorphisms Γ
---
paper_title: FORWARDING INDICES OF CARTESIAN PRODUCT GRAPHS

paper_content:

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.
---
paper_title: Multicommodity network flows—A survey

paper_content:

This report aims at a comprehensive survey of the literature dealing with the multicommodity flow problem. This problem arises naturally in network modelling wherever commodities, vehicles, or messages are to be shipped or transmitted from certain nodes of an underlying network to some others. Recent applications of mathematical programming techniques to traffic equilibrium problems in transportation studies as well as computer networks analysis has renewed considerable interest in this problem. This report discusses solution techniques for both linear and nonlinear flow problems. The former includes decomposition, partitioning, compact inverse methods, and primal-dual algorithms. Described is a variety of feasible direction methods for the latter. The report concludes by giving applications and computational experience for both types of problems.
---
paper_title: Laplacian spectra and invariants of graphs

paper_content:

For a connected graph G of order n ≥ 2 with positive Laplacian eigenvalues λ2,...,λn, let b(G) = n-1 1/λ2 + ... + 1/λn. In this note we derive bounds on some graph invariants (edge-density in cuts, isoperimetric number, mean distance, edge-forwarding index, edge connectivity, etc) in terms of b(G).
---
paper_title: Edge congestion and topological properties of crossed cubes

paper_content:

An n-dimensional crossed cube, CQ/sub n/, is a variation of hypercubes. In this paper, we give a new shortest path routing algorithm based on a new distance measure defined herein. In comparison with Efe's algorithm, which generates one shortest path in O(n/sup 2/) time, our algorithm can generate more shortest paths in O(n) time. Based on a given shortest path routing algorithm, we consider a new performance measure of interconnection networks called edge congestion. Using our shortest path routing algorithm and assuming that message exchange between all pairs of vertices is equally probable, we show that the edge congestion of crossed cubes is the same as that of hypercubes. Using the result of edge congestion, we can show that the bisection width of crossed cubes is 2/sup n-1/. We also prove that wide diameter and fault diameter are [n/2]+2. Furthermore, we study embedding of cycles in cross cubes and construct more types than previous work of cycles of length at least four.
---
paper_title: FORWARDING INDICES OF CARTESIAN PRODUCT GRAPHS

paper_content:

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.
---
paper_title: The forwarding indices of augmented cubes ✩

paper_content:

For a given connected graph G of order n, a routing R in G is a set of n(n-1) elementary paths specified for every ordered pair of vertices in G. The vertex (resp. edge) forwarding index of G is the maximum number of paths in R passing through any vertex (resp. edge) in G. Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2002) 71-84] proposed a variant of the hypercube Q"n, called the augmented cube AQ"n and presented a minimal routing algorithm. This paper determines the vertex and the edge forwarding indices of AQ"n as 2^n9+(-1)^n^+^19+n2^n3-2^n+1 and 2^n^-^1, respectively, which shows that the above algorithm is optimal in view of maximizing the network capacity.
---
paper_title: Forwarding index of cube-connected cycles

paper_content:

For a given connected graph G of order v, a routing R in G is a set of v(v-1) elementary paths specified for every ordered pair of vertices in G. The vertex (resp. edge) forwarding index of G is the maximum number of paths in R passing through any vertex (resp. edge) in G. Shahrokhi and Szekely [F. Shahrokhi, L.A. Szekely, Constructing integral flows in symmetric networks with application to edge forwarding index problem, Discrete Applied Mathematics 108 (2001) 175-191] obtained an asymptotic formula for the edge forwarding index of n-dimensional cube-connected cycle CCC"n as 54n^22^n(1-o(1)). This paper determines the vertex forwarding index of CCC"n as 74n^22^n(1-o(1)) asymptotically.
---
paper_title: Constructing Integral Uniform Flows in Symmetric Networks With Application to the Edge-Forwarding Index Problem

paper_content:

Abstract We study the integral uniform (multicommodity) flow problem in a graph G and construct a fractional solution whose properties are invariant under the action of a group of automorphisms Γ
---
paper_title: Edge-forwarding index of star graphs and other Cayley graphs

paper_content:

We present a technique for building, in some Cayley graphs, a routing for which the load of every edge is almost the same. This technique enables us to find the edge-forwarding index of star graphs and complete-transposition graphs.
---

Title: The Forwarding Indices of Graphs -- a Survey

Section 1: Introduction
Description 1: This section introduces the concept of forwarding indices in graphs and their importance in communication networks.

Section 2: NP-completeness
Description 2: This section discusses the complexity of computing forwarding indices and presents NP-completeness results for related problems.

Section 3: Basic Bounds and Relations
Description 3: This section covers theoretical bounds on forwarding indices and relationships between different types of forwarding indices in graphs.

Section 4: Optimal Graphs
Description 4: This section describes graphs that achieve optimal forwarding indices and includes related results and problems.

Section 5: For Cartesian Product Graphs
Description 5: This section investigates forwarding indices for graphs formed as Cartesian products of other graphs.

Section 6: Connectivity Constraint
Description 6: This section covers known results and bounds for the forwarding indices of k-connected or k-edge-connected graphs.

Section 7: Strongly Connected Digraphs
Description 7: This section extends the concept of forwarding indices to strongly connected digraphs and provides related results.

Section 8: Degree Constraint
Description 8: This section explores the forwarding indices of graphs with given degree constraints and includes specific results and bounds.

Section 9: Problems and Trivial Cases
Description 9: This section lists open problems and trivial cases related to forwarding indices in graphs.

Section 10: Difficulty, Methods and Relations to Other Topics
Description 10: This section addresses the challenges in determining forwarding indices, discusses methods used, and explores their relations to other topics in graph theory.

Section 11: Forwarding Indices of Some Graphs
Description 11: This section lists known forwarding indices for specific types of graphs and includes determined and conjectured values.