Linear time determination of the scattering number for strictly chordal graphs

Lilian Markenzon, Christina F. E. M. Waga

The scattering number of a graph $G$ was defined by Jung in 1978 as $sc(G)=max\{\omega (G-S)-|S|,S\subseteq V,\omega (G-S)\ne 1\}$ where $\omega (G-S)$ is the number of connected com…