Journal
INFORMATION PROCESSING LETTERS
Volume 172, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.ipl.2021.106157
Keywords
Hamiltonian cycle; Hypercube; Fault tolerance; Disjoint faulty edges
Categories
Ask authors/readers for more resources
This paper investigates hypercubes with pairwise disjoint faulty edges and proves that all other hypercubes are Hamiltonian when n >= 4, as long as there are two healthy crossing edges of different parity in each dimension.
We consider hypercubes with pairwise disjoint faulty edges. An n-dimensional hypercube Q(n) is an undirected graph with 2(n) nodes, each labeled with a distinct binary string of length n. The parity of the vertex is 0 if the number of ones in its label is even, and is 1 if the number of ones is odd. Two vertices a and b are connected by an edge iff a and b differ in one position. If a and b differ in position i, then we say that the edge (a, b) goes in dimension i and we define the parity of the edge as the parity of the end with 0 on the position i. It was already known that Q(n) is not Hamiltonian if all edges going in one dimension and of the same parity are faulty. In this paper we show that if n >= 4 then all other hypercubes are Hamiltonian. In other words, every cube Q(n), with n >= 4 and disjoint faulty edges is Hamiltonian if and only if for each dimension there are two healthy crossing edges of different parity. (C) 2021 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available