TY - JOUR
T1 - Rupture degree of graphs
AU - Li, Yinkui
AU - Zhang, Shenggui
AU - Li, Xueliang
PY - 2005/7
Y1 - 2005/7
N2 - We introduce a new graph parameter, the rupture degree. The rupture degree for a complete graph Kn is defined as 1 - n, and the rupture degree for an incomplete connected graph G 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 used to measure the vulnerability of networks. Rupture degrees of several specific classes of graphs are determined. Formulas for the rupture degree of join graphs and some bounds of the rupture degree are given. We also obtain some Nordhaus-Gaddum type results for the rupture degree.
AB - We introduce a new graph parameter, the rupture degree. The rupture degree for a complete graph Kn is defined as 1 - n, and the rupture degree for an incomplete connected graph G 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 used to measure the vulnerability of networks. Rupture degrees of several specific classes of graphs are determined. Formulas for the rupture degree of join graphs and some bounds of the rupture degree are given. We also obtain some Nordhaus-Gaddum type results for the rupture degree.
KW - Network vulnerability
KW - Nordhaus-Gaddum type result
KW - Rupture degree
UR - http://www.scopus.com/inward/record.url?scp=27944443645&partnerID=8YFLogxK
U2 - 10.1080/00207160412331336062
DO - 10.1080/00207160412331336062
M3 - 文章
AN - SCOPUS:27944443645
SN - 0020-7160
VL - 82
SP - 793
EP - 803
JO - International Journal of Computer Mathematics
JF - International Journal of Computer Mathematics
IS - 7
ER -