A lower bound for the distance \(k\)-domination number of trees (Q2581114)

The distance \(k\)-domination number \(\gamma_k(G)\) of a graph \(G\) is the size of the smallest subset \(D\) of nodes of \(G\) such that any node not in \(D\) has distance at most \(k\) from at least one node in \(D\). The authors show that if \(T\) is a tree with \(n\) nodes and \(t\) end-nodes, then \((2k+1)\gamma_k(T)\geq n+2k-kt\); and they characterize the trees for which equality holds.