Name
Title | ||
|---|---|---|
Matching preclusion and conditional edge-fault Hamiltonicity of binary de Bruijn graphs. |
Abstract | ||
|---|---|---|
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 n4 and classify all optimal matching preclusion sets and optimal conditional matching preclusion sets. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.dam.2017.07.039 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Binary de Bruijn graph,Edge-fault Hamiltonicity,Perfect matching,Matching preclusion set | Discrete mathematics,Combinatorics,Optimal matching,Vertex (geometry),Matching preclusion,Matching (graph theory),De Bruijn graph,De Bruijn sequence,Factor-critical graph,3-dimensional matching,Mathematics | Journal |
Volume | Issue | ISSN |
233 | C | 0166-218X |
Citations | PageRank | References |
3 | 0.38 | 23 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| ruizhi lin | 1 | 7 | 2.80 |
| Heping Zhang | 2 | 6 | 2.13 |