PIMS- UVic Discrete Math Seminar: Jules Hoepner

A broadcast on a connected graph G with vertex set V(G) is a function f:V(G) ➛ {0, 1, ..., diam(G)} such that f(v) ≤ e(v), where e(v) denotes the eccentricity of v. If f(v) > 0, the vertex v is said to broadcast at strength f(v). In generalizing independent sets to broadcasts, Erwin (2001) introduced the concept of hearing independent broadcasts, in which no broadcasting vertex u lies within distance f(v) of another broadcasting vertex v. If instead we require that the distance d(u, v) is at least f(u)+f(v) for all u, v with f(u), f(v) > 1, we obtain the definition of boundary independence introduced by Mynhardt and Neilson in 2019.

In this talk, we consider the minimum costs of maximal hearing independent and boundary independent broadcasts on graphs and show these parameters are comparable, solving an open problem posed by Marchessault and Mynhardt in 2021. We further prove that the minimum cost of a maximal boundary independent broadcast on a connected graph equals the minimum among those of its spanning trees, and that the same is true for hearing independent broadcasts.