Redundance of Trees

Abstract

The redundancy $R(G)$ of a graph $G$ is the minimum, over all dominating sets $S$, of $\sum _{v\in S}1+d(v)$, where $d(v)$ is the degree of vertex $v$. We establish a sharp upper bound on the redundancy of trees and characterize all trees that achieve the bound.