IMI/Publicaţii/CSJM/Ediţii/CSJM v.32, n.1 (94), 2024/

On the trees with maximum Cardinality-Redundance number

Authors: Elham Mohammadi, Nader Jafari Rad
Keywords: Dominating set, Cardinality-Redundance, trees.


A vertex $v$ is said to be over-dominated by a set $S$ if $|N[u]\cap S|\geq 2$. The cardinality--redundance of $S$, $CR(S)$, is the number of vertices of $G$ that are over-dominated by $S$. The cardinality--redundance of $G$, $CR(G)$, is the minimum of $CR(S)$ taken over all dominating sets $S$. A dominating set $S$ with $CR(S) = CR(G)$ is called a $CR(G)$-set. In this paper, we prove an upper bound for the cardinality--redundance in trees in terms of the order and the number of leaves, and characterize all trees achieving equality for the proposed bound.

Elham Mohammadi1, Nader Jafari Rad2
1;2Department of Mathematics
Shahed University Tehran, Iran
1Elham Mohammadi
E-mail: ,

2Nader Jafari Rad



Adobe PDF document0.18 Mb