Search

A recursive circulant graph G(N,d) has N = cdm vertices labeled from 0 to N - 1, where d ⩾ 2, m ⩾ 1, and 1 ⩽ c < d, and two vertices x,y ∈ G(N,d) are adjacent if and only if there is an integer k with 0 ⩽ k ⩽ ⌈logd N⌉ - 1 such that x ± dk ≡ y (mod N). With the aid of recursive structure, such class of graphs has many attractive features and was considered as a topology of interconnection networks for computing systems. The design of multiple independent spanning trees (ISTs) has many applications in network communication. For instance, it is useful for fault-tolerant broadcasting and secure message distribution. In the previous work of Yang et al. (2009), we provided a constructing scheme to build k ISTs on G(cdm,d) with d ⩾ 3, where k is the connectivity of G(cdm,d). However, the proposed constructing rules cannot be applied to the case of d = 2. For the integrity of solving the IST problem on recursive circulant graphs, this paper deals with the case of G(2m,2) using a set of different constructing rules. Especially, we show that the heights of ISTs for G(2m,2) are lower than the known optimal construction of hypercubes with the same number of vertices. [ABSTRACT FROM AUTHOR]

Two spanning trees rooted at vertex r in a graph G are called independent spanning trees (ISTs) if for each vertex v in G, v ≠ r, the paths from vertex v to vertex r in these two trees are internally distinct. If the connectivity of G is k, the IST problem is to construct k ISTs rooted at each vertex. The IST problem has found applications in fault-tolerant broadcasting, but it is still open for general graphs with connectivity greater than four. In this paper, we shall propose a very simple algorithm for solving the IST problem on multidimensional torus networks. In our algorithm, every vertex can determine its parent for a specific independent spanning tree only depending on its own label. Thus, our algorithm can also be implemented in parallel systems or distributed systems very easily. [ABSTRACT FROM AUTHOR]

This paper is concerned with a particular family of regular 4-connected graphs, called chordal rings. Chordal rings are a variation of ring networks. By adding two extra links (or chords) at each vertex in a ring network, the reliability and fault-tolerance of the network are enhanced. Two spanning trees on a graph are said to be independent if they are rooted at the same vertex, say, r, and for each vertex v ≠ r, the two paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees on a given graph is said to be independent if they are pairwise independent. Iwasaki et al. [9] proposed a linear time algorithm for finding four independent spanning trees on a chordal ring. In this paper, we give a new linear time algorithm to generate four independent spanning trees with a reduced height in each tree. Moreover, a complete analysis of our improvements on the heights of independent spanning trees is also provided. [ABSTRACT FROM AUTHOR]