| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419420 | Discrete Applied Mathematics | 2012 | 7 Pages |
For a connected graph GG, an edge set SS is a kk-restricted edge-cut if G−SG−S is disconnected and every component of G−SG−S has at least kk vertices. Graphs that allow kk-restricted edge-cuts are called λkλk-connected. The kk-edge-degree of a graph GG is the minimum number of edges between a connected subgraph HH of order kk and its complement G−HG−H. A λkλk-connected graph is called λkλk-optimal if its kk-restricted edge-connectivity equals its minimum kk-edge-degree and super-λkλk if every minimum kk-restricted edge-cut isolates a connected subgraph of order kk.In this paper we consider the cases k=2k=2 and k=3k=3. For triangle-free graphs that are not λkλk-optimal, we establish lower bounds for the order of components left by a minimum kk-restricted edge-cut in terms of the minimum kk-edge-degree. Sufficient conditions for a triangle-free graph to be λkλk-optimal and super-λkλk follow.
