کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871870 681668 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dominating plane triangulations
ترجمه فارسی عنوان
حاکمیت سهگانه هواپیما
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In 1996, Tarjan and Matheson proved that if G is a plane triangulated disc with n vertices, γ(G)≤n/3, where γ(G) denotes the domination number of G, i.e. the cardinality of the smallest set of vertices S such that every vertex of G is either in S or adjacent to a vertex in S. Furthermore, they conjectured that the constant 1/3 could be improved to 1/4 for a sufficiently large n. Their conjecture remains unsettled. In the present paper, it is proved that if G is a Hamiltonian plane triangulation with n vertices and minimum degree at least 4, then γ(G)≤max{⌈2n/7⌉,⌊5n/16⌋}. It follows immediately that if G is a 4-connected plane triangulation with n vertices, then γ(G)≤max{⌈2n/7⌉,⌊5n/16⌋}.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 211, 1 October 2016, Pages 175-182
نویسندگان
, , ,