Vulnerability parameters of split graphs
Authors:
- 1 January 2008
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 85 (1) , 19-23
Abstract
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
This publication has 9 references indexed in Scilit:
- Rupture degree of graphsInternational Journal of Computer Mathematics, 2005
- Computing the Scattering Number of GraphsInternational Journal of Computer Mathematics, 2002
- Scattering number in graphsNetworks, 2001
- A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial TimeJournal of Combinatorial Theory, Series B, 2000
- The toughness of split graphsDiscrete Mathematics, 1998
- Geometric Algorithms and Combinatorial Optimization1988
- On a class of posets and the corresponding comparability graphsJournal of Combinatorial Theory, Series B, 1978
- Graph Theory with Applications1976
- Tough graphs and hamiltonian circuitsDiscrete Mathematics, 1973