Sufficient conditions for λk-optimality in triangle-free graphs

AbstractFor a connected graph G=(V,E), an edge set S⊂E is a k-restricted edge cut if G−S is disconnected and every component of G−S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λk(G), is defined as the cardinality of a minimum k-restricted edge cut. For U1,U2⊂V(G), denote the set of edges of G with one end in U1 and the other end in U2 by [U1,U2]. Define ξk(G)=min{|[U,V(G)∖U]|:U⊂V(G),|U|=k≥1, and the subgraph induced by U is connected}. A graph G is λk-optimal if λk(G)=ξk(G). Let k be a positive integer, and let G be a connected triangle-free graph of order n≥2k. In this paper, we prove that (a) If d(u)+d(v)≥2⌊n+24⌋+1 for each pair u,v∈V(G) such that the distance between u and v is 2, then G is λ2-optimal; (b) If there are at least k common vertices in the neighbor sets of each pair of nonadjacent vertices in G, then G is λk-optimal