کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871210 | 1440180 | 2018 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Matching preclusion for n-grid graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A matching preclusion set of a graph is an edge set whose deletion results in a graph without perfect matchings or almost perfect matchings. The Cartesian product of n paths is called an n-grid graph. In this paper, we study the matching preclusion problems for n-grid graphs and obtain the following results. If an n-grid graph has an even order, then it has the matching preclusion number n, and every optimal matching preclusion set is trivial except for the case of P2mâ¡P3, the Cartesian product of a path on 2m vertices and a path on 3 vertices, when the nontrivial optimal matching preclusion sets are completely characterized. If the n-grid graph has an odd order, then it has the matching preclusion number n+1, and all the optimal matching preclusion sets are characterized.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 243, 10 July 2018, Pages 194-206
Journal: Discrete Applied Mathematics - Volume 243, 10 July 2018, Pages 194-206
نویسندگان
Qi Ding, Heping Zhang, Hui Zhou,