PIMS-UVic Discrete Math Seminar: Kiara McDonald

In Graph Theory, the well-known problems of packing and independence are generalized by broadcast packing and broadcast independence. As an analogy, placing cell towers (of various powers) in a network so that the signals do not interfere is a broadcast packing problem. Placing cell towers in a network where the signals can interfere at any point except the towers is a broadcast independence problem. In this talk, I will present explicit formulas for the broadcast independence and packing numbers of perfect binary and k-ary trees, along with the proof techniques used to determine these formulas. Furthermore, I will present a linear time algorithm for computing the broadcast independence number of spiders. This research was motivated by the question “Can we determine the broadcast independence number of other subclasses of the class of trees? In particular, what about k-ary trees?”, which was posed by Ahmane et al. in their paper On the broadcast independence number of caterpillars.

This is joint work with Dr. Richard Brewster.