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.

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.

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 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.

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.