In this paper, we show the explicit formula of the recurrence relation for the Tower of Hanoi on the star graph with four vertices, where the perfect tower of disks on a leaf vertex is transferred to the central vertex. This gives the solution to the problem posed at the 17th International Conference on Fibonacci Numbers and Their Applications[11]. Then, the recurrence relation are generalized to include the ones for the original 4-peg Tower of Hanoi and the Star Tower of Hanoi of transferring the tower from a leaf to another.

In this paper, we consider the problem of constructing a multicast tree in the star graph under the single-port communication model. Unlike previous studies for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme for the star graph of dimension n in 1.3125log2 n + O(log log n) time units. This running time is at most 1.3125 times of that of an optimal scheme.

The Recursively Decomposable Interconnection Network (RDIN) is a set of interconnection networks that can be recursively decomposed into smaller substructures whose topologies and properties are similar to the original one. The examples of the RDIN are hypercubes, star graph, mesh, tree, pyramid, pancake, and WK-recursive network. This paper proposed a uniform and simple model to represent the RDIN inside computers at first. Based on the model, a generalized and efficient allocation scheme capable of being applied to all the members of the RDIN is developed. The proposed scheme can fully recognize the substructures (such as subcube, substar, subtree,. . . ) more easily than ever, and it is the first one that can fully recognize all the incomplete substructures. The best-fit allocation is also proposed. The criterion aims at keeping the largest free parts from being destroyed, as is the philosophy of the best-fit allocation. Moreover, the proposed scheme can be performed in an injured RDIN with its processors and/or links faulty. Finally, the mathematical analysis and simulations for two instances, hypercubes and star graphs, of the RDIN are presented. The results show that the generalized scheme outperforms or is comparable to the other proprietary allocation schemes designed for the specific structure.

In this paper, we consider the ring embedding problem in faulty star graphs. Our embedding is based on the path transition scheme and node borrow technique in the ring of 4-dimensional substars with evenly distributed faults. Let Sn be the n-dimensional star graph having n! nodes. We will show that a ring of length n! - 2f can be found in Sn when the number of faulty nodes f is at most n-3. In the worst case, the loss of 2f nodes in the size of fault-free ring is inevitable because the star graph is bipartite. In addition, this result is superior to the best previous result that constructs the ring of length n! - 4f under the same fault condition. Moreover, by extending this result into the star graph with both node and edge faults simultaneously, we can find the fault-free ring of length n! - 2 fn in Sn when it contains fn faulty nodes and fe faulty edges such that fn + fe n-3.

We propose two fault-tolerant broadcasting schemes in star graphs. One of the schemes can tolerate up to n2 faults of the crash type in the n-star graph. The other scheme can tolerate up to (n3d1)/2 faults of the Byzantine type in the n-star graph, where d is the smallest positive integer satisfying nd!. Each of the schemes is designed for the single-port mode, and it completes the broadcasting in O(n log n) time. These schemes are time optimal. For the former scheme we analyze the reliability in the case where faults of the crash type are randomly distributed. It can tolerate (n!)α faults randomly distributed in the n-star graph with a high probability, where α is any constant less than 1.

The star graph has been known as an attractive alternative to the hypercube multiprocessor. Like the hypercube, the star graph possesses the properties of symmetry, partionability and fault tolerance, but with a smaller diameter and degree than those of the hypercube. When tasks arrive at the star graph, the tasks should be assigned appropriate free processors before execution. A new model, called Star graph (Sg)-lattice, is proposed to model the construction and free configuration of the star graph. Based on this model, the Sg-lattice scheme can fully recognize the substars. Finally, mathematical analyses and simulation results show that the Sg-lattice scheme outperforms the previous work in the storage and time complexities and the average allocation time.

This paper introduces an adaptive distributed routing algorithm for the faulty star graph. The algorithm is based on that the n-star graph has uniform node degree n-1 and is n-1-connected. By giving two routing rules based on the properties of nodes, an optimal routing function for the fault-free star graph is presented. For a given destination in the n-star graph, n-1 node-disjoint and edge-disjoint subgraphs, which are derived from n-1 adjacent edges of the destination, can be constructed by this routing function and the concept of Breadth First Search. When faults are encountered, according to that there are n-1 node-disjoint paths between two arbitrary nodes, the algorithm can route messages to the destination by finding a fault-free subgraphs based on the local failure information (the status of all its incident edges). As long as the number f of faults (node faults and/or edge faults) is less than the degree n-1 of the n-star graph, the algorithm can adaptively find a path of length at most d+4f to route messages successfully from a source to a destination, where d is the distance between source and destination.

In this paper, we consider the following node-to-set disjoint paths problem: given a node s and a set T = {t1,...,tk} of k nodes in a k-connected graph G, find k node-disjoint paths s ti, 1 i k. We give an O(n2) time algorithm for the node-to-set disjoint paths problem in n-dimensional star graphs Gn which are (n - 1)-connected. The algorithm finds the n - 1 node-disjoint paths of length at most d(Gn) + 1 for n 4,6 and at most d(Gn) + 2 for n = 4,6, where d(Gn) = 3(n-1)/2 is the diameter of Gn. d(Gn) + 1 and d(Gn) + 2 are also the lower bounds on the length of the paths for the above problem in Gn for n 4,6 and n = 4,6, respectively.