کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418514 681678 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A minimax result for perfect matchings of a polyomino graph
ترجمه فارسی عنوان
نتیجه کمینه بیشینه برای تطابق کامل یک نمودار polyomino
کلمات کلیدی
نمودار Polyomino؛ تطبیق کامل؛ مجموعه رزونانس؛ تعداد وادار کردن
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Let GG be a plane bipartite graph that admits a perfect matching. A forcing set for a perfect matching MM of GG is a subset SS of MM such that SS is not contained by other perfect matchings of GG. The minimum cardinality of forcing sets of MM is called the forcing number of MM, denoted by f(G,M)f(G,M). Pachter and Kim established a minimax result: for any perfect matching MM of GG, f(G,M)f(G,M) is equal to the maximum number of disjoint MM-alternating cycles in GG. For a polyomino graph HH, we show that for every perfect matching MM of HH with the maximum or second maximum forcing number, f(H,M)f(H,M) is equal to the maximum number of disjoint MM-alternating squares in HH. This minimax result does not hold in general for other perfect matchings of HH with smaller forcing number.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 206, 19 June 2016, Pages 165–171
نویسندگان
, ,