Vulnerability parameters of split graphs
Yinkui Li, Shenggui Zhang, Qilong Zhang · International Journal of Computer Mathematics · 2007
By rewriting the problem of computing the scattering number of a split graph as minimization of a submodular function on a crossing family, we show that this problem can be solved in polynomial time. At the same time, three other vulnerability parameters, namely, the integrity, tenacity and rupture degree of split graphs are determined.