کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9512131 1632452 2005 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Unique irredundance, domination and independent domination in graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Unique irredundance, domination and independent domination in graphs
چکیده انگلیسی
In this paper we prove that any graph with equal irredundance and domination numbers has a unique minimum irredundant set if and only if it has a unique minimum dominating set. Using a result by Zverovich and Zverovich [An induced subgraph characterization of domination perfect graphs, J. Graph Theory 20(3) (1995) 375-395], we characterize the hereditary class of graphs G such that for every induced subgraph H of G, H has a unique ι-set if and only if H has a unique γ-set. Furthermore, for trees with equal domination and independent domination numbers we present a characterization of unique minimum independent dominating sets, which leads to a linear time algorithm to decide whether such trees have unique minimum independent dominating sets.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 305, Issues 1–3, 6 December 2005, Pages 190-200
نویسندگان
, , ,