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.

Back to all abstracts