Sufficient conditions for triangle-free graphs to be optimally restricted edge-connected
For a connected graph G G , an edge set S S is a k k -restricted edge-cut if G?S G ? S is disconnected and every component of G?S G ? S has at least k k vertices. Graphs that allow k k -restricted edge-cuts are called ?k ? k -connected. The k k -edge-degree of a graphG G is the minimum number of edges between a connected subgraph H H of order k k and its complementG?H G ? H . A ?k ? k -connected graph is called ?k ? k -optimal if its k k -restricted edge-connectivity equals its minimum k k -edge-degree and super-?k ? k if every minimum k k -restricted edge-cut isolates a connected subgraph of order k k . In this paper we consider the cases k=2 k = 2 and k=3 k = 3 . For triangle-free graphs that are not ?k ? k -optimal, we establish lower bounds for the order of components left by a minimum k k -restricted edge-cut in terms of the minimum k k -edge-degree. Sufficient conditions for a triangle-free graph to be ?k ? k -optimal and super-?k ? k follow.
triangle-free graph restricted edge-connectivity ?k ? k -optimality ?k ? k ?k ? k ? k super-?k ? k ?k ? k ?k ? k ? k