کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871558 1440187 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Total domination stability in graphs
ترجمه فارسی عنوان
پایداری کل سلطه در نمودارها
کلمات کلیدی
سلطه کامل، ثبات سلطه کامل،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A set D of vertices in an isolate-free graph G is a total dominating set of G if every vertex is adjacent to a vertex in D. The total domination number, γt(G), of G is the minimum cardinality of a total dominating set of G. We note that γt(G)≥2 for every isolate-free graph G. A non-isolating set of vertices in G is a set of vertices whose removal from G produces an isolate-free graph. The γt−-stability, denoted stγt−(G), of G is the minimum size of a non-isolating set S of vertices in G whose removal decreases the total domination number. We show that if G is a connected graph with maximum degree Δ satisfying γt(G)≥3, then stγt−(G)≤2Δ−1, and we characterize the infinite family of trees that achieve equality in this upper bound. The total domination stability, stγt(G), of G is the minimum size of a non-isolating set of vertices in G whose removal changes the total domination number. We prove that if G is a connected graph with maximum degree Δ satisfying γt(G)≥3, then stγt(G)≤2Δ−1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 246-255
نویسندگان
, ,