Matching preclusion and conditional edge-fault Hamiltonicity of binary de Bruijn graphs

In interconnection networks, matching preclusion is a measure of robustness when there is a link failure. Let G be a graph with an even number of vertices. The matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching, and the conditional matching preclusion number of G is the minimum number of edges whose deletion results in a graph with no isolated vertices and without a perfect matching. In this paper, we study these problems for undirected binary de Bruijn graph UB(n). As an essential preparation, we obtain conditional edge-fault Hamiltonicity of binary de Bruijn graph B(n). Then we obtain matching preclusion number and conditional matching preclusion number of UB(n) for n >= 4 and classify all optimal matching preclusion sets and optimal conditional matching preclusion sets. (C) 2017 Elsevier B.V. All rights reserved.