In this paper, we extend known relationships between Cayley digraphs and their subgraphs and coset graphs with respect to subgroups to obtain a number of general results on homomorphism between them. Intuitively, our results correspond to synthesizing altemative, more economical, interconnection networks by reducing the number of dimensions and/or link density of existing networks via mapping and pruning. We discuss applications of these results to well-known and useful interconnection netorks such as hexagonal and honeycomb meshes, including the derivation of provably correct shortest-path routing algorithems for such networks.

The resistance distance rij between two vertices vi and t,,j of a (connected, molecular) graph G is equal to the resistance between the respective two points of all electrical network, constructed so as to correspond to G, such that the resistance of ally two adjacent points is unity. We show how the matrix elements rij call be expressed in terms of the Laplacian eigenvalues and eigenvectors of G. In addition, we determine certain properties of the resistance matrix R=||rij||.

In this paper, we propose a new class of interconnection networks, called "biswapped networks" (BSNs). Each BSN is built of 2n copies of some n-node basis network using a simple rule for connectivity that ensures its regularity, modularity, fault tolerance, and algorithmic efficiency. In particular, if the basis network is a Cayley digraph then so is the resulting BSN. Our proposed networks provide a systematic construction strategy for large, scalable, modular, and robust parallel architectures, while maintaining many desirable attributes of the underlying basis network that comprises its clusters. We show how key parameters of a BSN are related to the corresponding parameters of its basis network and obtain a number of results on internode distances, Hamiltonian cycles, and node-disjoint paths. We also discuss the relationship between BSNs and swapped or OTIS networks.

Despite numerous interconnection schemes proposed for distributed multicomputing, systematic studies of classes of inter-processor networks, that offer speed-cost tradeoffs over a wide range, have been few and far in between. A notable exception is the study of Cayley graphs that model a wide array of symmetric networks of theoretical and practical interest. Properties established for all, or for certain subclasses of, Cayley graphs are extremely useful in view of their wide applicability. In this paper, we obtain a number of new relationships between Cayley (di) graphs and their subgraphs and coset graphs with respect to subgroups, focusing in particular on homomorphism between them and on relating their internode distances and diameters. We discuss applications of these results to well-known and useful interconnection networks such as hexgonal and honeycomb meshes as well as certain classes of pruned tori.

We consider the relationships between Cayley digraphs and their coset graphs with respect to subgroups and obtain some general results on homomorphism and broadcasting between them. We also derive a general factorization theorem on subgraphs of Cayley digraphs by their automorphism groups. We discuss the applications of these results to well-known interconnection networks such as the butterfly network, the de Bruijn network, the cube-connected cycles network and the shuffle-exchange network.

Hypercube and Kautz network each possess certain desirable properties. However, some of the attractive features of one network are not found in the other. A novel class of network topologies proposed in this paper has the generalized hypercube and the Kautz network as its two extremes. The propsed network inberits the topological properties of both the Kautz network and extremes. The Propsed network inherits the topological properties of both the Kautz network and the generalized hypercube to a varying degree. This allows us to trade-off cost and performance effectively and construct networks which are most suitable for a particular purpose. In the present paper, we investigate the connectivity, wide-diameter, fault-tolerance, Hamiltonicity.

The clustering cofficient C of a network, Which is a measure of direct conuectivity between neighbors of the various nodes, ranges from O (for no connectivity) to 1 (for full connectivity). We define ex-tended clustering coefficients C (h) of a small-world network based on nodes that are at distance h from a source node, thus generalizing distance-1 neighborhoods employyed in computing the ordinary cluster-ing coefficient C = C(1). Based on known results about the distance distribution Pb(h) in a network, that is, the probability that a randomly chosen pair of vertices have distance h, we derive and experimentally validate the law Ps(h)C(h)< clogN/N, where c is a small constant that seldom exceeds 1. This result is significant because it shows that the product Ps(h)C(h) is upper-bouded by a value that is considerably smaller than the product of maximum values for Pb(h) and C(h).

In this short communicattion, we extend the known relation-ships between Cayley digraphs and their subgraphs and coset graphs with respect to subgroups and obtain some general results on homomor-phism and distance between them. Intuitively, Our results correspond to synthesizing alternative, more economical, interconnection networks by reducing the number of dimensions and/or link density of existing net-works via mapping and pruning. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honey comb meshes.

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted reat attention. A related and longtime unsolved problem is: for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained: (1) for any k 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k, e, c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k 0, an infinite family of singular k-tight optimal DLN can be constructed.

The resistance distance ri j between two vertices vi and vj of a (connected, molecular) graph G is equal to the effective resistance between the respective two points of an electrical network, constructed so as to correspond to G, such that the resistance of any edge is unity. We show how ri j can be computed from the Laplacian matrix L of the graph G: Let L(i) and L(i, j) be obtained from L by deleting its i-th row and column, and by deleting its i-th and j-th rows and columns, respectively. Then ri j=detL(i, j)/detL(i).