کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871210 1440180 2018 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Matching preclusion for n-grid graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Matching preclusion for n-grid graphs
چکیده انگلیسی
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
نویسندگان
, , ,