0
$\begingroup$

A definition of "separator" is the following: Let $G$ is an $n$-vertex graph, then $S\subseteq V(G)$ is a separator if there is a partition $V=A\cup B\cup S$ such that $|A|,|B|\le 2n/3$ and there is no edge of $G$ between $A$ and $B$.

If $G$ is $k$-vertex connected, then for any separator $S$, $|S|\ge k$. But what about the other way around, if any separator $S$ satisfying $|S|\ge t$, what can we say about the vertex-connectivity $\lambda$? Is $\lambda$ a function in $t$? (I don't quite understand the role of $2n/3$ in the definition of a separator.)

$\endgroup$
3
  • $\begingroup$ Join $K_{n-1}$ and $K_2$. A separator is large, but it is not even two-connected $\endgroup$ Commented Nov 28 at 15:11
  • $\begingroup$ I think after removing any two vertices of the join, the remaining is still connected? So it is 2-connected? $\endgroup$
    – Connor
    Commented Nov 28 at 16:25
  • $\begingroup$ I mean, join by a common vertex $\endgroup$ Commented Nov 28 at 16:29

0

You must log in to answer this question.

Browse other questions tagged .