کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872194 681622 2014 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Fractional acquisition in graphs
ترجمه فارسی عنوان
استخراج ذرات در نمودارها
کلمات کلیدی
اکتساب، حاکمیت، گرفتن نمودار، کسب مکرر،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let G be a vertex-weighted graph in which each vertex has weight 1. Given a vertex u with positive weight and a neighbor v whose weight is at least the weight on u, a fractional acquisition move transfers some amount of weight at u from u to v. The fractional acquisition number of G, written af(G), is the minimum number of vertices with positive weight after a sequence of fractional acquisition moves in G. In this paper, we determine the fractional acquisition number of all graphs: if G is an n-vertex path or cycle, then af(G)=⌈n/4⌉; if G is connected with maximum degree at least 3, then af(G)=1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 178, 11 December 2014, Pages 142-148
نویسندگان
,