4
$\begingroup$

[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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Cross-posted: math.stackexchange.com/questions/4461624/… $\endgroup$
    – RobPratt
    Commented 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$
    – Ilya Bogdanov
    Commented 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$
    – Ilya Bogdanov
    Commented 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
    Commented 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$
    – Ilya Bogdanov
    Commented Jun 1, 2022 at 3:51

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .