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