Abstract The star graph Sn proposed by Akers et al. has many advantages over the n‐cube. We show that when a large number of vertices are deleted from Sn the resulting graph can have at most two components, one of which is small. We use this result to solve a successive augmentation problem for Sn. This, in turn, provides extra choices for the topology of large interconnection networks. © 2002 Wiley Periodicals, Inc.

Akers et al. proposed an interconnection topology, the star graph, as an alternative to the popular n-cube. Cheng et al. proposed the split-star as an alternative to the star graph and a companion graph to the alternating group graph proposed by Jwo et al. Star graphs, alternating group graphs, and split-stars are advantageous over n-cubes in many aspects. Day and Tripathi proposed an assignment of directions to the edges of the star graph and showed that the resulting directed graph is strongly connected and has a simple routing algorithm. In this paper, we give simple routing algorithms for a proposed orientation of alternating group graphs and split-stars. The resulting directed graphs are not only strongly connected but they have maximal arc-fault tolerance and a small diameter. © 2000 John Wiley & Sons, Inc.

The problem of designing a sequence of optimal binary tests for the identification of a single faulty component is addressed. For components in linear order this is equivalent to the classical alphabetic coding problem solved by Hu and Tucker (1971). For partially ordered components the problem is solved by reduction to a minimization over a set of alphabetic problems.>

Conditions on the probability distributions of two sources that describe their relative uniformity are shown to be sufficient for inequalities on their minimum average codeword lengths and entropies. The Huffman coding problem and variants involving Renyi entropy are addressed.>

Source distributions that can be encoded with zero redundancy for the case of unequal code symbol costs are examined. These distributions provide a natural generalization of the binary, equal costs case for which these distributions are the dyadic distributions. These zero redundancy codes have the property that the expected proportion of codeword symbols given by a particular letter is equal to an experimental function of the code letter cost. The converse is not true in general; however, partial converse results hold. Maximum-entropy zero-redundancy distributions are easily identified through their connection with unequal cost coding for uniform sources.>