کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649950 | 1342471 | 2008 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Restrained bondage in graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Restrained bondage in graphs Restrained bondage in graphs](/preview/png/4649950.png)
چکیده انگلیسی
Let G=(V,E)G=(V,E) be a graph. A set S⊆VS⊆V is a restrained dominating set if every vertex not in SS is adjacent to a vertex in SS and to a vertex in V−SV−S. The restrained domination number of GG, denoted by γr(G)γr(G), is the smallest cardinality of a restrained dominating set of GG. We define the restrained bondage number br(G)br(G) of a nonempty graph GG to be the minimum cardinality among all sets of edges E′⊆EE′⊆E for which γr(G−E′)>γr(G)γr(G−E′)>γr(G). Sharp bounds are obtained for br(G)br(G), and exact values are determined for several classes of graphs. Also, we show that the decision problem for br(G)br(G) is NP-complete even for bipartite graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 23, 6 December 2008, Pages 5446–5453
Journal: Discrete Mathematics - Volume 308, Issue 23, 6 December 2008, Pages 5446–5453
نویسندگان
Johannes H. Hattingh, Andrew R. Plummer,