We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
1-Vertex-Hamiltonian-Laceability of Hypercubes with Maximal Edge Faults.
- Authors
Sun-Yuan Hsieh; Che-Nan Kuo
- Abstract
Suppose that G = (V0 ∪ V1, E) is a bipartite graph with two partite sets V0 and V1 of equal size. Let x and y be two arbitrary distinct, vertices and let w be another vertex different from x and y. G is said to be 1-vertex-Hamiltonian-laceable if G - w satisfies the following three properties: P1. There is a (|V0| + |V1| - 2)-length path between x and y, where x and y are in the same partite set and w is in the other partite set; P2. There is a (|V0| + |V1| - 3)-length path between x and y, where x and y are in different partite sets and w is in any partite set; P3. There is a (|V0| + |V1| - 4)-length path between x and y, where x, y, w are in the same partite set. Let Fe be the set of faulty edges of an n-dimensional hypercube Qn. In this paper, we show that Qn - Fe (the graph obtained by deleting all edges of Fe from Qn) remains 1-vertex-Hamiltonian-laceable when |Fe| ≤ n - 3.
- Subjects
HYPERCUBE networks (Computer networks); GRAPH theory; BIPARTITE graphs; PARALLEL processing; DISTRIBUTED computing; HAMILTONIAN graph theory
- Publication
Journal of Interconnection Networks, 2005, Vol 6, Issue 4, p407
- ISSN
0219-2659
- Publication type
Article
- DOI
10.1142/S0219265905001496