[Posted this first at math stackexchange, but it probably fits better here.]

I am looking for references about the following problem.

Given a (connected) bipartite graph $G$, find an independent set $M$ minimizing the ratio $|\partial M|/|M|$.

Here, $\partial M$ denotes the set of neighbours of $M$.
An independent set is a set $M$ of vertices such that $(\partial M)\cap M = \emptyset$.

More specifically, I am looking for information about the class of bipartite graphs trees $G= (A\,\dot{\cup}\, B \,, E)$ for which $A$ is the unique solution to the problem above.

Examples of such graphs include lines with an odd number of vertices, or, more generally, trees in which every $b\in B$ has degree two.

  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/questions/4461624/… $\endgroup$
    – RobPratt
    May 31, 2022 at 1:07
  • 2
    $\begingroup$ A trivial note: If $M$ is an optimal independent set, then one of $M\cap A$ and $M\cap B$ is also such. So, for the specific question, it suffices to check separately subsets of $A$ and $B$ only. $\endgroup$ May 31, 2022 at 8:18
  • 2
    $\begingroup$ Another observation: the ‘specific’ condition is satisfied iff $|B|<|A|$, and $|\partial B’|>\frac{|A|}{|B|}\cdot |B’|$ for every$\varnothing\neq B’\subsetneq B$. $\endgroup$ May 31, 2022 at 8:33
  • $\begingroup$ @IlyaBogdanov: Indeed so (but it should be $|\partial A'| > \frac{|B|}{|A|}\cdot |A'|$ for $\emptyset \ne A'\subsetneq A$ in your second comment). I have managed to prove some things about these graphs (e.g., they must be acyclic), but I'm not graph theorist and don't know the literature on the subject, so I'm afraid that I'm spending time on stuff that is already known... $\endgroup$
    – Erik D
    Jun 1, 2022 at 0:36
  • $\begingroup$ @BikD In your formula, there should be a $<$ sogn instead of $>$; and I meant exactly what I meant, that was the reason of putting that into a comment. As for the second part of your comment --- I don't understand acyclicity, as a complete bipartite graph (with parts of different size) firs into the condition... $\endgroup$ Jun 1, 2022 at 3:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.