In this paper, we consider the problem of multicasting a message in k-ary n-cubes under the store-and-forward model. The objective of the problem is to minimize the size of the resultant multicast tree by keeping the distance to each destination over the tree the same as the distance in the original graph. In the following, we first propose an algorithm that grows a multicast tree in a greedy manner, in the sense that for each intermediate vertex of the tree, the outgoing edges of the vertex are selected in a non-increasing order of the number of destinations that can use the edge in a shortest path to the destination. We then evaluate the goodness of the algorithm in terms of the worst case ratio of the size of the generated tree to the size of an optimal tree. It is proved that for any k 5 and n 6, the performnance ratio of the greedy algorithm is c kn - o(n) for some constant 1/12 c 1/2.

This paper first proposes a new approach to designing high-quality, low-diameter, small mean-internode-distance (MID), k-subcubic-connected cyclic networks. The approach is a modification of the k-cubic-connected cyclic (k-ccc) network in which there are N=k2k-1 instead of N=k2k nodes in the k-ccc network. The special features of this network are: (1) It fills the gap between the number of nodes in k-ccc and (k+1)-ccc networks, but retains a constant number of link (3) per node in the network, (2) it allows higher quality, smaller diameters and mean internode distances hypercube networks with the same numbers of nodes. A second novel approach consists of a k+-sccc network with the same number of nodes as the k-ccc but with smaller diameters and mean internode distances. A generalized k-ccc network formed by nodes N=k2m is introduced for n-cube and k-ccc (modified or normal) networks that allows minimum network quality to be obtained where m may or may not equal to k. A routing algorithm for 4-sccc is also presented.

We give an explicit formula for the number of n-variable clique function in terms of the parameters based upon the numbers of intersecting antichains of the lower half of the n-cube. We present the numbers of clique functions with up to seven variables through computer evaluation of the parameters.

The n-dimensional hypercube is a highly concurrent loosely coupled multiprocessor based on the binary n-cube topology. This paper is concerned with the following basic graph-theoretic question: given a graph G = (V, E), is it an exact n-cube? We propose an O (|E|) hypercube recognition algorithm using some new topological properties of the hypercube graph.