Computing and Bounding the Scattering Number of Graphs

Abstract

In this thesis we study the scattering number of graphs, a parameter introduced by Jung in 1978, from two different perspectives. First, we investigate it under a computational lens, proving that the scattering number of bipartite and planar graphs cannot be computed in polynomial time unless P=NP, but that the scattering number of graphs with bounded tree-width can be computed in polynomial time. Secondly, we focus on upper bounding the scattering number of graphs in special graph classes. In particular, we obtain bounds on the scattering number of planar graphs with given vertex-connectivity and minimum degree. These are generalizations of lower bounds on the matching number of such graphs obtained by Baybars and Nishizeki in 1979 and our proof strategy is strongly inspired by theirs. We further generalize these results by bounding the scattering number of maximally K5-minor-free graphs with minimum degree at least four, but this result relies on a substantially different and somewhat more involved proof. All bounds we derive are tight up to constant additive terms.