"Balanced" separator which is independent set

Question

I am looking for existence results on separators of $r$-regular graphs $G=(V,E)$, which have the property that

• $S\subset V$ is a separator
• for all $v,w\in S$ the edge $\langle v,w\rangle\not\in E$ (i.e., an independent set)
• (nice to have) the connected components of $G-S$ have "similar size"

Obviously, this does not exist for graphs which are "too dense", e.g., the complete graph does not contain such a set but I am only looking for cases where $r$ is a lot smaller than $\frac{n}{2}$. The stronger version where every minimal separator is an independent set is discussed in https://cstheory.stackexchange.com/questions/16428/graphs-in-which-every-minimal-separator-is-an-independent-set. But for the simple existence, is this something that has already been of interest in the literature and are there results on the existence of such a $S$?

EDIT: Also $S$ does not need to be minimal. The "balanced" condition should ensure that for example in a triangle free graph with small degree, e.g., $3$ or $4$ with many vertices one could separate away a single vertex by putting all its neighbors in $S$, which would satisfy the first two conditions.

Answer 1

This is not a full answer but only a sketch of an idea too long for a comment.

I think that such $S$ will not exist when $r$ is already a small constant. (Possibly $r=3$ but the sketch that I provide could succeed with $r = 6$). Filling the gaps in the sketch would require more precise computations with graph expansion.

First take a $k$-regular bipartite graph $H = (A \cup B,E')$ which is a good expander and $A$ and $B$ are of a same size $n' = n/2$ . (I think of $k = 3$ and $E'$ as a union of $k$ random disjoint matchings.) First let me assume that I have a separator $S$ as you want for this graph. (In this case such a separator exists, for example $S = A$ but I want to derive some properties.)

Let $S[A] := S \cap A$ and $S[B]$ is defined analogously. If both $S[A]$ and $S[B]$ are too small, then I believe that there will be a big component in $A \cup B \setminus S$ from the expansion. (This is perhaps the weakest part of the sketch to make this precise. An intuition is that there are many edges between $A \setminus S[A]$ and $B \setminus S[B]$.) Here I think of too small as smaller than $n'/2$, say, but it may depend on the actual expansion properties.

Thus at least one of $S[A]$, $S[B]$ is big, say that the size of $S[A]$ is at least $n'/2$. By expansion, this means that the size of $S[B]$ has to be quite small, otherwise we have an edge between $S[A]$ and $S[B]$ which is not allowed in $S$. I think of quite small as smaller than $n'/4$.

Now note that the ideas above are resistent to adding adges to $H$. We add edges between vertices of $A$ and as well we add edges between vertices of $B$. Namely, on $A$ we build a smaller copy of our construction: A bipartite $k$-regular expander and similarly on $B$. We still assume (WLOG) that $S[A]$ is larger after adding edges, thus $S[B]$ is small. Inside $S[B] \setminus B$, this should mean that we have a big component $C[B]$ (by ideas as above applied to the smaller expander on $B$). Now again by expansion (now on $H$), either $A \setminus S[A]$ is small and $C[B]$ is big already in $S \setminus A \cup B$, or $A \setminus S[A]$ is a bit larger but then there are edges between $C[B]$ and most of the vertices of $A \setminus S[A]$. Thus $C[B]$ extends to a big component in $S \setminus A \cup B$.