Vulnerability parameters of split graphs

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.

Keywords:

• Integrity
• Rupture degree
• Scattering number
• Split graph
• Submodular function
• Tenacity

Acknowledgements

This work was supported by NSFC (No. 60642002) and SRF for ROCS of SEM.