On the trees with maximum Cardinality-Redundance number
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 d...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2024-04-01
|
| Series: | Computer Science Journal of Moldova |
| Subjects: | |
| Online Access: | http://www.math.md/files/csjm/v32-n1/v32-n1-(pp38-45).pdf |
| Summary: | 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. |
|---|---|
| ISSN: | 1561-4042 2587-4330 |