Sufficient Conditions for a Graph to be λ_k-Optimal with Given Girth and Diameter

摘要

An edge set S is a k-restricted edge cut of a connected graph G if G- S is no longer connected and every component of G-S has at least k vertices. The k-restricted edge connectivity of G, denoted by λ_k(G), is the cardinality of a minimum k-restricted edge cut. A graph G with λ_k(G) = ξ_k(G) is called λ_j-optimal, where ξ_k(G) = min{|[U, U]| | UCV(G), U = k and G[U] is connected}, [U, U] is the number of edges between U and U, G[U] is the subgraph of G induced by U. In this article, we give a sufficient condition for a graph to be λ_k-optimal: for any integer k≥3, every graph G with girth g≥5, minimum degree δ≥ k, and diameter D≤g - 4 when g is even and D≤g - 3 when g is odd is λ_k-optimal. Furthermore, if δ≥2k-3, the diameter condition can be relaxed a little to D≤g - 3 no matter whether g is even or odd. This generalizes a result of Balbuena et al. [Sufficient conditions for λ-optimality in graphs with girth g, J Graph Theory 52 (2006) 73-86], and improves a result of Fabrega and Fiol in a sense [On the extraconnectivity of graphs, Discrete Math 155 (1996) 49-57].