Article ID Journal Published Year Pages File Type
9512131 Discrete Mathematics 2005 11 Pages PDF
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
, , ,