In information dissemination problem on interconnection networks, problems of broadcasting and gossiping have been widely studied. In this paper, we study the other problem, called multi-source broadcasting, defined as follows: there are some (but not all) vertices each of which has the unique item of information and needs to disseminate to every other vertex. This problem is located at an intermediate position between broadcasting and gossiping. We analyze the multi-source broadcasting problem on the cycle-rooted tree and the de Bruijn digraph as an interconnection network.

Abstract The k‐degree Cayley graph has been proposed by Hsieh and Hsiao (Networks 47 (2006), 26–36). They have shown that the k‐degree Cayley graph is actually a Cayley graph. According to their definition, a generating set of that graph was defined implicitly. Therefore, it requires some effort to figure out that such graphs are actually Cayley graphs. In this article, we use the wreath product of groups to show that k‐degree Cayley graphs form a class of Cayley graphs. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

We introduce a new model for diagnosable systems called (t, k)-diagnosable system which guarantees that at least k faulty units (processors) in a system are detected provided that the number of faulty units does not exceed t. This system includes classical one-step diagnosable systems and sequentially diagnosable systems. We prove a necessary and sufficient condition for (t, k)-diagnosable system, and discuss a lower bound for diagnosability. Finally, we deal with a relation between (t, k)-diagnosability and diagnosability of classical basic models.

In this paper, we count small cycles in generalized de Bruijn digraphs. Let n = pdh, where d ??? p, and gl = gcd(d1 - 1, n). We show that if p < d3 and k ≤ ⌊logd n⌋ + 1, or p > d3 and k ≤ h + 3, then the number of cycles of length k in a generalized de Bruijn digraph GB(n, d) is given by 1/k Σl/k μ(k/l)gl⌈d1/gl⌉, where μ is the Möbius function and ⌈r⌉ denotes the smallest integer not smaller than a real number r. © 1997 John Wiley & Sons, Inc.