Author： Li Yinkui
Publisher： Taylor & Francis Ltd
ISSN： 0020-7160
Source： International Journal of Computer Mathematics, Vol.85, Iss.11, 2008-11, pp. : 1629-1635
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
For the complete graph Kn, its rupture degree is defined as 1-n; and for a noncomplete connected graph G, its rupture degree is defined by r(G)=max{ω(G - X)-|X|-m(G - X):X ⊂ V(G), ω(G - X) > 1 }, where ω(G - X) is the number of components of G - X and m(G - X) is the order of a largest component of G - X. It is shown that this parameter can be well used to measure the vulnerability of networks. Li and Li proved in 2004 that computing the rupture degree for a general graph is NP-complete. In this paper, we give a recursive algorithm for computing the rupture degree of trees, and determine the maximum and minimum rupture degree of trees with given order and maximum degree.
Related content
By Li Yinkui
International Journal of Computer Mathematics, Vol. 82, Iss. 7, 2005-07 ,pp. :
Access to resources
Recommend
By Fujisawa Jun
Graphs and Combinatorics, Vol. 26, Iss. 5, 2010-09 ,pp. :
Asymptotics of trees with a prescribed degree sequence and applications
RANDOM STRUCTURES AND ALGORITHMS, Vol. 44, Iss. 3, 2014-05 ,pp. :
Differential Equations, Vol. 41, Iss. 2, 2005-02 ,pp. :