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

摘要

AbstractIn interconnection networks, matching preclusion is a measure of robustness when there is a link failure. LetGbe a graph with an even number of vertices. The matching preclusion number ofGis the minimum number of edges whose deletion leaves the resulting graph without a perfect matching, and the conditional matching preclusion number ofGis 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 graphUB(n). As an essential preparation, we obtain conditional edge-fault Hamiltonicity of binary de Bruijn graphB(n). Then we obtain matching preclusion number and conditional matching preclusion number ofUB(n)forn?4and classify all optimal matching preclusion sets and optimal conditional matching preclusion sets.]]>