Abstract | ||
---|---|---|
The arrangement graph An,k, which is a generalization of the star graph (n-t=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 we 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)-1, 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 |F3 |⩽k |
Year | DOI | Venue |
---|---|---|
1997 | 10.1109/ICPADS.1997.652625 | ICPADS |
Keywords | Field | DocType |
major design parameter,faulty arrangement graphs,arrangement graph,star graph,edge faults,leq k,fault tolerant computing,proven hamiltonian,fault-tolerant ring embedding,vertex faults,design parameters,performance evaluation,edge fault,vertex fault,hypercube networks,computer science,fault tolerant,hypercubes,fault tolerance | Graph,Embedding,Vertex (geometry),Hamiltonian (quantum mechanics),Computer science,Star (graph theory),Fault tolerance,Hypercube,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-8186-8227-2 | 3 | 0.42 |
References | Authors | |
8 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sun-Yuan Hsieh | 1 | 1715 | 112.85 |
Gen-Huey Chen | 2 | 979 | 89.32 |
Chin-Wen Ho | 3 | 573 | 39.27 |