Fault-Tolerant Hamiltonicity of the WK-Recursive Networks

Author

Ho, Tung-Yang ; Lin, Cheng-Kuan ; Tan, Jimmy J M ; Hsu, Lih-Hsing

Author_Institution

Dept. of Inf. Manage., Ta Hwa Inst. of Technol., Hsinchu, Taiwan

fYear

2009

fDate

14-16 Dec. 2009

Firstpage

592

Lastpage

595

Abstract

Many research on the WK-recursive network has been published during the past several years due to its favorite properties. In this paper, we consider the fault-tolerant hamiltonian connectivity of the WK-recursive network. We use K(d, t) to denote the WK-recursive network of level t, each of which basic modules is a d-vertex complete graph. The fault-tolerant hamiltonian connectivity is defined to be the maximum integer k such that G is k fault-tolerant hamiltonian connected if G is hamiltonian connected and is undefined otherwise. In this paper, we prove that the fault-tolerant hamiltonian connectivity of K(d, t) is d-4.

Keywords

computer networks; fault tolerance; graph theory; recursive functions; WK-recursive networks; d-vertex complete graph; fault-tolerant hamiltonian connectivity; fault-tolerant hamiltonicity; maximum integer; Computer science; Fault tolerance; Fault tolerant systems; Hafnium; Information management; Multiprocessor interconnection networks; Network topology; Parallel architectures; fault-tolerant hamiltonian; hamiltonian; hamiltonian connected;

fLanguage

English

Publisher

ieee

Conference_Titel

Pervasive Systems, Algorithms, and Networks (ISPAN), 2009 10th International Symposium on

Conference_Location

Kaohsiung

Print_ISBN

978-1-4244-5403-7

Type

conf

DOI

10.1109/I-SPAN.2009.116

Filename

5381666