Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648749 | Discrete Mathematics | 2008 | 11 Pages |
For a connected graph G, the r th extraconnectivity κr(G)κr(G) is defined as the minimum cardinality of a cutset X such that all remaining components after the deletion of the vertices of X have at least r+1r+1 vertices. The standard connectivity and superconnectivity correspond to κ0(G)κ0(G) and κ1(G)κ1(G), respectively. The minimum r-tree degree of G , denoted by ξr(G)ξr(G), is the minimum cardinality of N(T)N(T) taken over all trees T⊆GT⊆G of order |V(T)|=r+1|V(T)|=r+1, N(T)N(T) being the set of vertices not in T that are neighbors of some vertex of T . When r=1r=1, any such considered tree is just an edge of G . Then, ξ1(G)ξ1(G) is equal to the so-called minimum edge-degree of G , defined as ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, where d(u)d(u) stands for the degree of vertex uu. A graph G is said to be optimally r -extraconnected, for short κrκr-optimal, if κr(G)⩾ξr(G)κr(G)⩾ξr(G). In this paper, we present some sufficient conditions that guarantee κr(G)⩾ξr(G)κr(G)⩾ξr(G) for r⩾2r⩾2. These results improve some previous related ones, and can be seen as a complement of some others which were obtained by the authors for r=1r=1.