کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872036 | 681717 | 2016 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On dominating sets of maximal outerplanar and planar graphs
ترجمه فارسی عنوان
در مجموعه های غالب مجموعه های بیرونی حداکثر و نقشه های مسطح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A set DâV(G) of a graph G is a dominating set if every vertex vâV(G) is either in D or adjacent to a vertex in D. The domination number γ(G) of a graph G is the minimum cardinality of a dominating set of G. Campos and Wakabayashi (2013) and Tokunaga (2013) proved independently that if G is an n-vertex maximal outerplanar graph having t vertices of degree 2, then γ(G)â¤n+t4. We improve their upper bound by showing γ(G)â¤n+k4, where k is the number of pairs of consecutive 2-degree vertices with distance at least 3 on the outer cycle. Moreover, we prove that γ(G)â¤5n16 for a Hamiltonian maximal planar graph G with nâ¥7 vertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 164-169
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 164-169
نویسندگان
Zepeng Li, Enqiang Zhu, Zehui Shao, Jin Xu,