"Discrete Mathemetics Top Cited Article 2005-2010"

The restricted connectivity κ′(G)κ′(G) of a connected graph G is defined as the minimum cardinality of a vertex-cut over all vertex-cuts X such that no vertex uu has all its neighbors in X; the superconnectivity κ1(G)κ1(G) is defined similarly, this time considering only vertices uu in G-XG-X, hence κ1(G)⩽κ′(G)κ1(G)⩽κ′(G). The minimum edge-degree of G is ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, d(u)d(u) standing for the degree of a vertex uu. In this paper, several sufficient conditions yielding κ1(G)⩾ξ(G)κ1(G)⩾ξ(G) are given, improving a previous related result by Fiol et al. [Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17–31] and guaranteeing κ1(G)=κ′(G)=ξ(G)κ1(G)=κ′(G)=ξ(G) under some additional constraints.

Peer Reviewed

Award-winning