Diameter-sufficient conditions for a graph to be super-restricted connected

摘要

A vertex-cut X is said to be a restricted cut of a graph G if it is a vertex-cut such that no vertex it in G has all its neighbors in X. Clearly, each connected component of G-X must have at least two vertices. The restricted connectivity kappa'(G) of a connected graph G is defined as the minimum cardinality of a restricted cut. Additionally, if the deletion of a minimum restricted cut isolates one edge, then the graph is said to be super-restricted connected. In this paper, several sufficient conditions yielding super-restricted-connected graphs are given in terms of the girth and the diameter. The corresponding problem for super-edge-restricted-connected graph is also studied. (C) 2007 Elsevier B.V. All rights reserved.