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 \left\{ \sum_{v \in S} (1 + \deg v) :S\subseteq V \text{and} [N(x) \cap S] \geq 1 \quad \forall x \in V \right\},\)
\(\text{F}(G) = \max \left\{ \sum_{v \in S} (1 + \deg v) :S\subseteq V \text{and} [N(x) \cap S] \leq 1 \quad \forall x \in V \right\}.\)
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.