Hamiltonian cycles in hypercubes with faulty edges. Issue 4 (2nd October 2018)

• Record Type: Journal Article
• Authors: Dybizbański, Janusz; Szepietowski, Andrzej
• Is Part Of: International journal of computer mathematics. Volume 3:Issue 4(2018)
• Page Start: 244
• Page End: 261
• Publication Date: 2018-10-02
• Subjects: Hamiltonian cycle -- hypercube -- fault tolerance -- local traps; 05C45; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2018.1538164
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: Szepietowski [12] observed that the hypercube is not Hamiltonian if it contains a trap disconnected halfway. A proper subgraph T is disconnected halfway if at least half of its nodes have parity 0 (or 1, resp.) and all edges joining the nodes of parity 0 (or 1, resp.) in T with nodes outside T, are faulty. In this paper, we describe all traps disconnected halfway T with the size and we consider the problem whether there exist small sets of faulty edges that are not based on sets disconnected halfway and still preclude Hamiltonian cycles. We show that if with the set of faulty edges F contains a trap disconnected halfway T that is of size and is minimal, then T is a path or is Hamiltonian. We also describe heuristic that recognizes nonhamiltonian cubes, also these ones that do not contain traps disconnected halfway.