Article ID Journal Published Year Pages File Type
1710457 Applied Mathematics Letters 2006 5 Pages PDF
Abstract

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 GG, its edge-connectivity is δ(G)δ(G), and its edge-toughness is min{δ(G),|E(G)||V(G)|−1}, where δ(G)δ(G), V(G)V(G) and E(G)E(G), are the minimum degree, the vertex set and the edge set of GG, 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.

Related Topics
Physical Sciences and Engineering Engineering Computational Mechanics
Authors
, ,