کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949471 | 1440190 | 2017 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Matching preclusion and conditional edge-fault Hamiltonicity of binary de Bruijn graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 233, 31 December 2017, Pages 104-117
Journal: Discrete Applied Mathematics - Volume 233, 31 December 2017, Pages 104-117
نویسندگان
Ruizhi Lin, Heping Zhang,