4
$\begingroup$

Let $G$ be a graph with vertex set $[n]$. I say that a subset $S \subset [n]$ is a cut set of $G$ if $c(S \setminus \{i\})<c(S)$ for every $i \in S$, where $c(S)$ denotes the number of connected components of $G[[n] \setminus S]$ (the subgraph induced in $G$ by $[n] \setminus S$). I assume that the empty set is a cut set of any graph.

Is something known about cut sets of a graph (maybe under a different name)? If so, what are good references for this?

If I require that $G$ is bipartite and for every cut set $S$ of $G$, $c(S)=card(S)+1$, is it true that the intersection of any two cut sets is again a cut set?

I know that the answer to the last question is negative if $G$ is not bipartite or the other condition does not hold.

Thanks!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I guess another term would be "minimal r-way vertex cut set" for any r, where r-way means removal disconnects into r connected components. I've seen "vertex cut set" used to distinguish from "edge cut set." In the traditional usage, "cut set" simply means that removal disconnects the graph. Finding cut sets is important in computer science, and a common problem is to find minimal ones. So yes, I think this has been studied before. $\endgroup$
    – David White
    Commented Jan 23, 2017 at 15:33
  • $\begingroup$ Does the definition of the OP even make sense? Just writing it out, using the OP's defintion, we find $c(S\setminus\{i\})$ $=$ number of connected components of $G[ [n] \setminus (S\setminus\{i\})]$ $=$ $G[ ([n]\setminus S) \cup \{i\}]$, and now the OP defines their "cut sets" as those $S$ for which this has fewer connected components than $G[[n]\setminus S]$, while obvious this number is at least as large. $\endgroup$
    – Peter Heinig
    Commented Sep 24, 2017 at 18:58
  • $\begingroup$ So, it seems that, taking the OP literally, the answer to "Is something known about cut sets of a graph (maybe under a different name)?" is 'Yes, it is known that they don't exist.'. Am I missing something? $\endgroup$
    – Peter Heinig
    Commented Sep 24, 2017 at 18:58
  • $\begingroup$ @PeterHeinig I think the definition makes sense. Consider the path graph $P_3$ and $S=\{2\}$. If we remove $S$, then the induced subgraph has $2$ connected components. If we remove $S\backslash \{2\}=\varnothing$, then the induced subgraph has $1$ connected component, and this number is smaller than $2$. $\endgroup$
    – Philipp Lampe
    Commented Aug 21, 2018 at 8:03

1 Answer 1

Reset to default
-1
$\begingroup$

Intersection of "cut sets" in your usage (or the typical usage, which is just a set whose removal disconnects the graph) need not result in another cutset. Consider for instance a cycle (e.g., $C_6$) and the sets $\{1,3\}$ and $\{1,4\}$.

Edit:

Oh! Sorry. I missed that extra condition you wanted about number of components. Do you have some bipartite graphs doing that other than a path?

Improve this answer
$\endgroup$
1

You must log in to answer this question.

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