Jules Hoepner

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