On k-ary n-cubes: theory and applications Original Research Article

Many parallel processing applications have communication patterns that can be viewed as graphs called k-ary n-cubes, whose special cases include rings, hypercubes and tori. In this paper, combinatorial properties of k-ary n-cubes are examined. In particular, the problem of characterizing the subgraph of a given number of nodes with the maximum edge count is studied. These theoretical results are then applied to compute a lower bounding function in branch-and-bound partitioning algorithms and to establish the optimality of some irregular partitions.