TY - JOUR
T1 - Edge vulnerability parameters of split graphs
AU - Zhang, Qilong
AU - Zhang, Shenggui
PY - 2006/9
Y1 - 2006/9
N2 - A graph is called a split graph if its vertex set can be partitioned into a clique and an independent set. In this work, we investigate three vulnerability parameters of split graphs when edges are removed, i.e., edge-connectivity, edge-toughness and edge-integrity. It is proved that, for a noncomplete connected split graph G, its edge-connectivity is δ (G), and its edge-toughness is min {δ (G), frac(| E (G) |, | V (G) | - 1)}, where δ (G), V (G) and E (G), are the minimum degree, the vertex set and the edge set of G, respectively. Furthermore, we show that the edge-integrity of a noncomplete connected split graph equals its order when its minimum degree is greater than half of the size of its largest clique.
AB - A graph is called a split graph if its vertex set can be partitioned into a clique and an independent set. In this work, we investigate three vulnerability parameters of split graphs when edges are removed, i.e., edge-connectivity, edge-toughness and edge-integrity. It is proved that, for a noncomplete connected split graph G, its edge-connectivity is δ (G), and its edge-toughness is min {δ (G), frac(| E (G) |, | V (G) | - 1)}, where δ (G), V (G) and E (G), are the minimum degree, the vertex set and the edge set of G, respectively. Furthermore, we show that the edge-integrity of a noncomplete connected split graph equals its order when its minimum degree is greater than half of the size of its largest clique.
KW - Edge-connectivity
KW - Edge-integrity
KW - Edge-toughness
KW - Split graph
UR - http://www.scopus.com/inward/record.url?scp=33744931643&partnerID=8YFLogxK
U2 - 10.1016/j.aml.2005.09.011
DO - 10.1016/j.aml.2005.09.011
M3 - 文章
AN - SCOPUS:33744931643
SN - 0893-9659
VL - 19
SP - 916
EP - 920
JO - Applied Mathematics Letters
JF - Applied Mathematics Letters
IS - 9
ER -