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

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