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.
Citation
David R.Guichard. Redundance of Trees[J], Ars Combinatoria, Volume 070. 297-300. .