Fault-tolerant ring embedding in faulty arrangement graphs

Sun yuan Hsieh, Gen Huey Chen, Chin Wen Ho

Research output: Contribution to conferencePaperpeer-review

3 Citations (Scopus)

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
Publication statusPublished - 1997 Dec 1
EventProceedings of the 1997 International Conference on Parallel and Distributed Systems - Seoul, South Korea
Duration: 1997 Dec 101997 Dec 13

Other

OtherProceedings of the 1997 International Conference on Parallel and Distributed Systems
CitySeoul, South Korea
Period97-12-1097-12-13

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

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

Cite this