# Broadcast Domination and Irredundance

###
Kieka Mynhardt

University of Victoria

PDF

**Minisymposium:**
GRAPH DOMINATION

**Content:**
A \emph{broadcast} on a nontrivial connected graph $G=(V,E)$ is a function
$f:V\rightarrow\{0,1,\dots,$ $\operatorname{diam}G\}$ such that $f(v)\leq
e(v)$ (the eccentricity of $v$) for all $v\in V$. The \emph{cost} of $f$ is
$\sigma(f)=\sum_{v\in V}f(v)$. A broadcast $f$ is a \emph{dominating broadcast
}if every vertex of $G$ is within distance $f(v)$ from a vertex $v$ with
$f(v)>0$. A dominating broadcast $f$ is a \emph{minimal dominating broadcast}
if no broadcast $g\neq f$ such that $g(v)\leq f(v)$ for each $v\in V$ is
dominating. The \emph{lower and upper broadcast numbers} of $G$ are defined
by
\[
\gamma_{b}(G)=\min\left\{ \sigma(f):f\text{ is a dominating broadcast of
}G\right\} \text{ and}%
\]%
\[
\Gamma_{b}(G)=\max\left\{ \sigma(f):f\text{ is a minimal dominating broadcast
of }G\right\} .
\]
A dominating broadcast is minimal dominating if and only if it satisfies
\begin{enumerate}
\item[$\mathbf{P}_{\min}$:] For each $v$ such that $f(v)>0$ there exists $u\in
V$ that is not dominated by the broadcast $f^{\prime}=(f-\{(v,f(v)\})\cup
\{(v,f(v)-1)\}$.
\end{enumerate}
A broadcast that satisfies $\mathbf{P}_{\min}$ is an \emph{irredundant
broadcast}, and may or may not also be dominating. An irredundant broadcast
$f$ is \emph{maximal irredundant }if no broadcast $g\neq f$ such that
$g(v)\geq f(v)$ for each $v\in V$ is irredundant. The \emph{lower and upper
broadcast irredundant numbers }of $G$ are\emph{ }%
\[
\operatorname{ir}_{b}(G)=\min\left\{ \sigma(f):f\text{ is a maximal
irredundant broadcast of }G\right\} \text{ and}%
\]%
\[
\operatorname{IR}_{b}(G)=\max\left\{ \sigma(f):f\text{ is an irredundant
broadcast of }G\right\} .
\]
We discuss properties of these concepts and the relationships between their
associated parameters.