کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875618 | 1441976 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Strong matching preclusion number of graphs
ترجمه فارسی عنوان
تعدیل شدید تطبیق تعداد نمودارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شبکه های اتصال تطبیق کامل، تعداد تکرار پذیری قوی تطبیق
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. The strong matching preclusion number (or simply, SMP number) smp(G) of a graph G is the minimum number of vertices and/or edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem and has been introduced by Park and Ihm. In this paper, we first study the SMP number of some special graph classes, and give some sharp upper and lower bounds of SMP number. Next, graphs with large and small SMP number are characterized, respectively. In the end, we investigate the Nordhaus-Gaddum-type relations on SMP number.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 713, 22 February 2018, Pages 11-20
Journal: Theoretical Computer Science - Volume 713, 22 February 2018, Pages 11-20
نویسندگان
Yaping Mao, Zhao Wang, Eddie Cheng, Christopher Melekian,