51³Ô¹Ï

Topic

Broadcast Independence and Broadcast Packing

Department of Mathematics and Statistics

Date & location

• Friday, July 11, 2025
• 10:00 A.M.
• Clearihue Building, Room B019

Examining Committee

Supervisory Committee

• Dr. Jing Huang, Department of Mathematics and Statistics, 51³Ô¹Ï (Co-Supervisor)
• Dr. Richard Brewster, Department of Mathematics and Statistics, UVic (Co-Supervisor)

External Examiner

• Dr. Kathie Cameron, Department of Mathematics, Wilfrid Laurier University

Chair of Oral Examination

• Dr. Eva Kwoll, Department of Geography, UVic

Abstract

For a simple, connected graph 𝐺, a broadcast on 𝐺 is a function 𝑓:𝑉(𝐺)→ℕ, where 𝑓(𝑣)≤𝑒𝑐𝑐_𝐺(𝑣) for every vertex 𝑣∈𝑉(𝐺), and the weight of 𝑓 is 𝑓(𝑉)=Σ_{𝑣∈𝑉(𝐺)}𝑓(𝑣). A vertex 𝑣 is broadcasting if 𝑓(𝑣)>0 and a vertex 𝑢 hears 𝑣 if 𝑑(𝑢,𝑣)≤𝑓(𝑣). An independent broadcast is a broadcast in which no broadcasting vertex hears another vertex. A packing broadcast is a broadcast where no vertex hears more than one vertex. The broadcast independence number 𝛼_𝑏(𝐺), respectively the broadcast packing number 𝑃_𝑏(𝐺), is the maximum weight over all independent broadcasts, respectively packing broadcasts, of 𝐺. In this thesis, we examine these two broadcast parameters in different classes of graphs.

Determining the broadcast independence number is NP-hard for planar graphs of maximum degree 4, and before this thesis, the best known algorithm to compute the broadcast independence number of a tree of order n had time complexity 𝒪(𝑛⁹), due to Bessy and Rautenbach. In this thesis, we improve the time complexity of computing the broadcast independence number of a tree to 𝒪(𝑛⁶) time. We achieve this through the use of the ball catch graph and maximum weighted independent sets in this graph. This method is also applied to diamond-free interval graphs, paw-free interval graphs, strongly chordal split graphs and several other subclasses of chordal and weakly chordal graphs, showing that the broadcast independence number of such graphs of order 𝑛 can be found in 𝒪(𝑛⁶) time. Further, we establish exact values of 𝛼_𝑏(𝐺) of proper interval graphs and subclasses of split graphs.

We also examine the broadcast packing problem in this thesis. By the work of Farber and Lubiw, computing the broadcast packing number of strongly chordal graphs is known to be polynomial time solvable. In contrast, we establish the NP-hardness of the broadcast packing problem in split graphs. We also determine the exact value of the broadcast packing number of proper interval graphs and subclasses of split graphs.