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 𝑇.