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

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.

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

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.