• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Boundary Independent Broadcasts in Graphs

Hoepner, Jules 08 December 2022 (has links)
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

Page generated in 0.1083 seconds