## Abstract

The arrangement graph A_{n,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 |F_{e}| and |F_{v}| denote the numbers of edge faults and vertex faults, respectively. We show that A_{n,k} is hamiltonian when (1) (k = 2 and n-k≥4, or k≥3 and n-k≥4+[k/2]), and |F_{e}|≤k(n-k)-2, or (2) k≥2, n-k≥2+[k/2], and |F_{e}|≤k(n-k-3)-1, or (3) k≥2, n-k≥3, and |F_{e}|≤k.

Original language | English |
---|---|

Pages | 744-749 |

Number of pages | 6 |

Publication status | Published - 1997 Dec 1 |

Event | Proceedings of the 1997 International Conference on Parallel and Distributed Systems - Seoul, South Korea Duration: 1997 Dec 10 → 1997 Dec 13 |

### Other

Other | Proceedings of the 1997 International Conference on Parallel and Distributed Systems |
---|---|

City | Seoul, South Korea |

Period | 97-12-10 → 97-12-13 |

## All Science Journal Classification (ASJC) codes

- Hardware and Architecture