Bounds on the Total Redundance and Efficiency of a Graph

Abstract

For a graph $G$ with vertex set $V$, the total redundance, $\text{TR}(G)$, and efficiency, $\text{F}(G)$, are defined by the two expressions:
$\text{TR}(G)=min\{\sum _{v\in S}(1+\mathrm{deg}v):S\subseteq V\text{and}[N(x)\cap S]\ge 1\mathrm{\forall }x\in V\},$
$\text{F}(G)=max\{\sum _{v\in S}(1+\mathrm{deg}v):S\subseteq V\text{and}[N(x)\cap S]\le 1\mathrm{\forall }x\in V\}.$
That is, $\text{TR}$ measures the minimum possible amount of domination if every vertex is dominated at least once, and $\text{F}$ measures the maximum number of vertices that can be dominated if no vertex is dominated more than once.

We establish sharp upper and lower bounds on $\text{TR}(G)$ and $\text{F}(G)$ for general graphs $G$ and, in particular, for trees, and briefly consider related Nordhaus-Gaddum-type results.