Double domination and super domination in trees
Balakrishna Krishnakumari, Yanamandram Balasubramanian Venkatakrishnan · Discrete Mathematics Algorithms and Applications · 2016
A vertex of a graph [Formula: see text] is said to dominate itself and all its neighbors. A double dominating set (DDS) of a graph [Formula: see text] is a set [Formula: see text] of vertices such that every vertex of [Formula: see text] is dominated by at least two vertices of [Formula: see text]. The double domination number of a graph [Formula: see text] is the minimum cardinality of a DDS of [Formula: see text]. For a graph [Formula: see text], a subset [Formula: see text] of [Formula: see text] is a super dominating set SDS if for every vertex of [Formula: see text] there exists an external private neighbor of [Formula: see text] with respect to [Formula: see text]. The super domination number of [Formula: see text] is the minimum cardinality of a SDS of [Formula: see text]. We prove that for every tree [Formula: see text], [Formula: see text], and we characterize the trees attaining this bound.