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.

Many real networks, including those in social, technological, and biological realms, are small-world networks. The two distinguishing characteristics of small-world networks are high local clustering and small average internode distance. A great deal of previous research on small-world networks has been based on probabilistic methods, with a rather small number of researchers advocating deterministic models. In this paper, we further the study of deterministic small-world networks and show that Cayley graphs may be good models for such networks. Small-world networks based on Cayley graphs possess simple structures and significant adaptability. The Cayley-graph model has pedagogical value and can also be used for designing and analyzing communication and the other real networks.

An n-node network, with nodes numbered 0 to n-1, is an undirected double-loop network with chord lengths 1 and s (2≤s＜hi2) when each node i (0≤i＜n) is connected to each of the four nodes i±1 and i±s via an undirected link; all node-index expressions are evaluated modulo n. Let n=qs+r, where r (0≤r＜s) is the remainder of dividing n by s. Furthermore, let s=ar+b, where b (0≤b＜r) is the remainder of dividing s by r. In this paper, we provide closed-form formulas for the diameter of a double-loop network for the case q＞r and for a subcase of the case q≤r when b≤aq+1. In the complementary subcase of q≤r, when b＞aq+1, network diameter can be derived by applying the O(log n)-time algorithm of Zerovnik and Pisanski (J.Algorithms, Vol. 14, pp. 226-243, 1993). Obtaining a closed-form formula for diameter of the double-loop network in the latter subcase remains an open problem.

Despite numerous interconnection schemes proposed for distributed multicomputing, systematic studies of classes of interprocessor 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 hexagonal and honeycomb meshes as well as certain classes of pruned tori.

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.