Boundary and Hearing Independent Broadcasts in Graphs and Trees

Christina M. Mynhardt, Gary MacGillivray, Jules Hoepner

Publication date: 4 May 2023

Abstract: A broadcast on a connected graph G with vertex set V(G) is a function $f:V(G) ightarrow {0, 1, ..., ext{diam}(G)}$ such that $f(v)leq e(v)$ (the eccentricity of $v$) for all $vin V$. A vertex $v$ is said to be broadcasting if $f(v)>0$, with the set of all such vertices denoted $V_f^+$. A vertex $u$ hears $f$ from $vin V_f^+$ if $d_G(u, v)leq f(v)$. The broadcast $f$ is 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 $vin V_f^+$, the broadcast is said to be boundary independent. The cost of $f$ is $sigma(f)=sum_{vin V(G)}f(v)$. The minimum cost of a maximal boundary independent broadcast on G, called the lower bn-independence number, is denoted $i_{bn}(G)$. The 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 G and show that $i_h(G)/i_{bn}(G)$ is bounded. For both parameters, we show that the lower bn-independence number (h-independence number) of a 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 branch vertices of T. We conclude by describing a polynomial-time algorithm to determine $alpha_{bn}(T)$ for a given tree T.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

This page was built for publication: Boundary and Hearing Independent Broadcasts in Graphs and Trees