# Jules Hoepner

- BSc (University of Victoria, 2020)

## Topic

**Boundary Independent Broadcasts in Graphs**

Department of Mathematics and Statistics

## Date & location

- Tuesday, November 22, 2022
- 2:30 P.M.
- David Strong Building, Room C130

## Reviewers

### Supervisory Committee

- Dr. Kieka Mynhardt, Department of Mathematics and Statistics, University of Victoria (Co-Supervisor)
- Dr. Gary MacGillivray, Department of Mathematics and Statistics, UVic (Co-Supervisor)

### External Examiner

- Dr. Linda Neilson, Adult Basic Education, Vancouver Island University

### Chair of Oral Examination

- Dr. Aaron Gulliver, Department of Electrical and Computer Engineering, UVic

## Abstract

A broadcast on a connected graph 𝐺with vertex set 𝑉(𝐺) is a function 𝑓 ∶ 𝑉(𝐺) → {0,1,…,diam(𝐺)} such that 𝑓(𝑣) ≤ 𝑒(𝑣), where 𝑒(𝑣) denotes the eccentricity of 𝑣. A vertex 𝑣 is said to be broadcasting if 𝑓(𝑣) > 0. The cost of 𝑓 is 𝜎(𝑓) = Σ_{𝑣∈𝑉(𝐺)}𝑓(𝑣), or the sum of the strengths of the broadcasts on the set of broadcasting vertices 𝑉_{𝑓}^{+ }= {𝑣 ∈ 𝑉(𝐺) ∶ 𝑓(𝑣) > 0}. A vertex 𝑢 hears 𝑓 from 𝑣 ∈ 𝑉_{𝑓}^{+} if 𝑑_{𝐺}(𝑢,𝑣) ≤ 𝑓(𝑣). The broadcast 𝑓 is hearing independent if no broadcasting vertex hears another. If, in addition, any vertex 𝑢 that hears 𝑓 from multiple broadcasting vertices satisfies 𝑓(𝑉) ≤ 𝑑_{𝐺}(𝑢,𝑣) for all 𝑣 ∈ 𝑉_{𝑓}^{+}, the broadcast is said to be boundary independent.

The minimum cost of a maximal boundary independent broadcast on 𝐺, called the lower bn-independence number, is denoted 𝑖_{𝑏𝑛}(𝐺). The lower h-independence number 𝑖_{ℎ}(𝐺) is defined analogously for hearing independent broadcasts. We prove that 𝑖_{𝑏𝑛}(𝐺) ≤ 𝑖_{ℎ}(𝐺) for all graphs 𝐺, and show that 𝑖_{ℎ}(𝐺)/𝑖_{𝑏𝑛}(𝐺) 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 𝐺 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 𝛼_{𝑏𝑛}(𝐺). We show 𝛼_{𝑏𝑛}(𝐺) can be bounded in terms of the independence number 𝛼(𝐺), 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 𝛼_{𝑏𝑛}(𝑇) when 𝑇 is a tree in terms of its order and the number of vertices of degree at least 3, known as the branch vertices of 𝑇. We conclude by describing a polynomial-time algorithm to determine 𝛼_{𝑏𝑛}(𝑇) for a given tree 𝑇.