کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650739 1342500 2008 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On domination and reinforcement numbers in trees
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On domination and reinforcement numbers in trees
چکیده انگلیسی

The reinforcement number of a graph is the smallest number of edges that have to be added to a graph to reduce the domination number. We introduce the k-reinforcement number of a graph as the smallest number of edges that have to be added to a graph to reduce the domination number by k  . We present an O(k2n)O(k2n) dynamic programming algorithm for computing the maximum number of vertices that can be dominated using γ(G)-kγ(G)-k dominators for trees. A corollary of this is a linear-time algorithm for computing the k-reinforcement number of a tree. We also discuss extensions and related problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 7, 6 April 2008, Pages 1165–1175
نویسندگان
, , , , , ,