A \textit{broadcast} on a connected graph $G$ with vertex set $V(G)$ is a function $f:V(G)\rightarrow \{0, 1, ..., \text{diam}(G)\}$ such that $f(v)\leq e(v)$, where $e(v)$ denotes the eccentricity of $v$. A vertex $v$ is said to be \textit{broadcasting} if $f(v)>0$. The \textit{cost} of $f$ is $\sigma(f)=\sum_{v\in V(G)}f(v)$, or the sum of the strengths of the broadcasts on the set of broadcasting vertices $V_f^+=\{v\in V(G)\,:\,f(v)>0\}$. A vertex $u$ \textit{hears} $f$ from $v\in V_f^+$ if $d_G(u, v)\leq f(v)$. The broadcast $f$ is \textit{hearing independent} if no broadcasting vertex hears another. If, in addition, any vertex $u$ that hears $f$ from multiple broadcasting vertices satisfies $f(v)\leq d_G(u, v)$ for all $v\in V_f^+$, the broadcast is said to be \textit{boundary independent.}
The minimum cost of a maximal boundary independent broadcast on $G$, called the \textit{lower bn-independence number}, is denoted $i_{bn}(G)$. The \textit{lower h-independence number} $i_h(G)$ is defined analogously for hearing independent broadcasts. We prove that $i_{bn}(G)\leq i_h(G)$ for all graphs $G$, and show that $i_h(G)/i_{bn}(G)$ is bounded, finding classes of graphs for which the two parameters are equal. For both parameters, we show that the lower bn-independence number (h-independence number) of an arbitrary connected graph $G$ equals the minimum lower bn-independence number (h-independence number) among those of its spanning trees.
We further study the maximum cost of boundary independent broadcasts, denoted $\alpha_{bn}(G)$. We show $\alpha_{bn}(G)$ can be bounded in terms of the independence number $\alpha(G)$, and prove that the maximum bn-independent broadcast problem is NP-hard by a reduction from the independent set problem to an instance of the maximum bn-independent broadcast problem.
With particular interest in caterpillars, we investigate bounds on $\alpha_{bn}(T)$ when $T$ is a tree in terms of its order and the number of vertices of degree at least 3, known as the \textit{branch vertices} of $T$. We conclude by describing a polynomial-time algorithm to determine $\alpha_{bn}(T)$ for a given tree $T$. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/14556 |
| Date | 08 December 2022 |
| Creators | Hoepner, Jules |
| Contributors | MacGillivray, Gary, Mynhardt, Christina |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0023 seconds