Fault-tolerant ring embedding in faulty arrangement graphs

Sun yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Research output: Contribution to conferencePaperpeer-review

3 Scopus citations

Abstract

The arrangement graph An,k, which is a generalization of the star graph (n-k = 1), presents more flexibility than the star graph in adjusting the major design parameters: number of nodes, degree, and diameter. Previously the arrangement graph has proven hamiltonian. In this paper the further show that the arrangement graph remains hamiltonian even if it is faulty. Let |Fe| and |Fv| denote the numbers of edge faults and vertex faults, respectively. We show that An,k is hamiltonian when (1) (k = 2 and n-k≥4, or k≥3 and n-k≥4+[k/2]), and |Fe|≤k(n-k)-2, or (2) k≥2, n-k≥2+[k/2], and |Fe|≤k(n-k-3)-1, or (3) k≥2, n-k≥3, and |Fe|≤k.

Original languageEnglish
Pages744-749
Number of pages6
StatePublished - 1997
EventProceedings of the 1997 International Conference on Parallel and Distributed Systems - Seoul, South Korea
Duration: 10 Dec 199713 Dec 1997

Conference

ConferenceProceedings of the 1997 International Conference on Parallel and Distributed Systems
CitySeoul, South Korea
Period10/12/9713/12/97

Fingerprint

Dive into the research topics of 'Fault-tolerant ring embedding in faulty arrangement graphs'. Together they form a unique fingerprint.

Cite this