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

چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 308, Issue 7, 6 April 2008, Pages 1165–1175
نویسندگان
Jean R.S. Blair, Wayne Goddard, Stephen T. Hedetniemi, Steve Horton, Patrick Jones, Grzegorz Kubicki,