Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9512131 | Discrete Mathematics | 2005 | 11 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Miranca Fischermann, Lutz Volkmann, Igor Zverovich,