The construction of optimal K-fault-tolerant designs for token rings

Abstract

Designing an optimal K-fault-tolerant network for token rings is equivalent to constructing an optimal k-hamiltonian graph, where k is a positive interger and corresponds to the number of faluts.In this paper, we propose a construction scheme for the optimal k-hamiltonian graphs for every positive integer k. Applying this scheme, we can easily construct a family of optimal k-hamiltonian graphs with diameter 2logd-1 n-O(1),where n is the number of vertices and d is the maximum degree. This diameter equals 2 times of Moore bound.