A set of nodes (which are processors or communication centers), with links between some of them for the purposes of communicating data or messages is usually represented by a graph. Instead of speaking of nodes and links, we speak of vertices and edges. For a given 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, 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). The expanding factors of graphs are the edge and vertex cutset expansion. Intuitively, expanding factors are measures of connectivity and the forwarding indices ,the statistics on paths. In this paper, we give bounds on expanding factors and forwarding indices in digraphs and in product graphs, furthermore, we calculate the expanding factors and forwarding indices for some specific graphs.
|