1
$\begingroup$

An edge cut is a set of edges that, if removed from a connected graph, will disconnect the graph.

For a connected graph $G=(V ,E)$, an edge set $S ⊂ E$ is a $k$-restricted-edge-cut, if $G−S$ is disconnected and every connected component of $G−S$ has at least $k$ vertices.

We can see the concept of $k$- restricted-edge-cuts is one of generalizations of edge cuts. The restricted edge connectivity was proposed by Esfahanian and Hakimi in [1].

[1] Esfahanian A H, Hakimi S L. On computing a conditional edge-connectivity of a graph[J]. Information processing letters, 1988, 27(4): 195-199. doi.org/10.1016/0020-0190(88)90025-7

PS (Off-topic remarks): They give a polynomial algorithm for computing the $2$- restricted-edge-cut of graphs. But I feel that it may not be correct. I have been trying to implement this algorithm, but failed, see

For example, we have a graph as follows.

enter image description here

Then we can check that the edge set $\{(0,1),(0,2)\}$ is a minimum $2$-restricted-edge-cut of the above graph (we note that any cut edge $(0,4)$ or $(0,5)$ is not $2$-restricted-edge-cut).

A minimal edge cut set is an edge cut where no subset is also a cut set.

I know that the following claim holds.

  • A edge cut $S$ is a minimal edge cut if and only if $G-S$ have exactly two connected components.

So a natural question is:

Question. If $S$ is a minimum (or minimal) $k$-restricted-edge-cut of $G$, then must $G-S$ have exactly two connected components?

I am looking for counterexamples (or prove it).

$\endgroup$
7
  • $\begingroup$ If we take three instances of complete graph $K_r$ and connect them in pairs by three edges $S=\{e_1,e_2,e_3\}$. We obtain a connected graph $G$. The graph $G-S$ consists of three connected components. Is this not a counterexample for $k=r$? $\endgroup$
    – kabenyuk
    Jan 19 at 14:20
  • $\begingroup$ Now is $S$ a minimum $r$-restricted-edge-cut? ($\{e_1,e_2\}$ is an $r$-restricted-edge-cut with fewer edges than $S$.) I hope I understand correctly. $\endgroup$
    – licheng
    Jan 19 at 14:30
  • 1
    $\begingroup$ I agree with you. Indeed, if $S$ is minimal cut and $u\in S$, then graph $H=G-S+u$ is still connected, but then graph $H-u=G-S$ has exactly two connected components. Right? $\endgroup$
    – kabenyuk
    Jan 19 at 15:30
  • $\begingroup$ Yes. A minimal edge cut set is an edge cut where no subset is also a cut set. In fact, I was just asking if a minimum $k$-restricted-edge-cut is always a minimal cut. (Note that there is a difference between the meaning of "minimum" and "minimal".) $\endgroup$
    – licheng
    Jan 19 at 15:41
  • $\begingroup$ It is not very clear how a minimum cut can be a non-minimal cut. $\endgroup$
    – kabenyuk
    Jan 19 at 16:05

1 Answer 1

Reset to default
1
$\begingroup$

For brevity, use "CC" for "connected component".

A edge cut $S$ is a minimal edge cut if and only if $G-S$ have exactly two CCs.

While the "only if" direction is true, the "if" direction is wrong since $S$ may contain redundant edges. For example, consider a graph with vertices $a,b,c,d$ and edges $ab,bc,cd,db$. Edge cut $\{ab, bc\}$ is not minimal since $\{ab\}$ is an edge cut, too. Both edge sets "cut" the graph into two CCs.

If $S$ is a minimal $k$-restricted-edge-cut of $G$, then must $G−S$ have exactly two CCs?

Of course. Otherwise $G-S$ has at least three CCs. Since $G$ is connected, there is an edge $e$ in $G$ between two of those CCs. $e$ must be in $S$. Consider $S'=S-\{e\}$. Here are the CCs of $G-S'$:

  • Every CC in $G-S$ other than those two CCs connected by $e$.
  • the union of those two CCs in $G-S$ connected by $e$ together with $e$

So $G-S'$ has two CCs. That means $G-S'$ is disconnected. Each CC of $G-S'$ is either a CC of $G-S$ or the union of two CCs of $G-S$ together with $e$. Hence, $S'$ is also a $k$-restricted edge cut, which contradicts with the minimality of $S$.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much. I got the theorem involving bonds mixed up by mistake. (Bondy text, 2008, Theorem, 2.15 (P62)) In a connected graph $G$, a nonempty edge cut $∂(X)$ is a bond if and only if both $G[X]$and $G[V\setminus X]$ are connected. The definition of edge cuts in Bondy book there is a little different. $\endgroup$
    – licheng
    Jan 22 at 5:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .