Name
Abstract | ||
|---|---|---|
The extraconnectivity κ ( n ) of a simple connected graph G is a kind of conditional connectivity which is the minimum cardinality of a set of vertices, if any, whose deletion disconnects G in such a way that every remaining component has more than n vertices. The usual connectivity and superconnectivity of G correspond to κ (0) and κ (1), respectively. This paper gives sufficient conditions, relating the diameter D , the girth g , and the minimum degree δ of a graph, to assure maximum extraconnectivity. For instance, if D ⩽ g - n + 2( δ - 3), for n ⩾ 2 δ + 4 and g ⩾ n + 5, then the value of κ ( n ) is ( n - 1) δ - 2 n , which is optimal. The corresponding edge version of this result, to assure maximum edge-extraconnectivity λ ( n ), is also discussed. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0012-365X(96)00218-X | Discrete Mathematics |
Keywords | Field | DocType |
large minimum degree,connected graph | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Cardinality,Connectivity,Mathematics | Journal |
Volume | ISSN | Citations |
167-168, | Discrete Mathematics | 11 |
PageRank | References | Authors |
0.66 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. Balbuena | 1 | 212 | 26.94 |
| A. Carmona | 2 | 87 | 10.62 |
| J. Fàbrega | 3 | 305 | 22.43 |
| M. A. Fiol | 4 | 816 | 87.28 |