Please note: This master’s thesis presentation will take place online.
Dinis Arsénio Nunes Vitorino, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Therese Biedl
We will study the scattering number of graphs. After some brief motivation, we will see how easy/hard it is to compute the scattering number of graphs from structured graphs classes. Secondly, we will derive upper bounds on the scattering number of graphs, again under structural assumptions. In particular, we will bound the scattering number of planar graphs with given vertex-connectivity and minimum degree. These are generalizations of lower bounds on their matching number obtained by Baybars and Nishizeki in 1979. We will additionally get a glimpse of how these results can be generalized into bounds on the scattering number of maximally K5-minor-free graphs with minimum degree at least four.