A maximal independent set of a graph $G$ is a subset of vertices $S$ such that each vertex of $G$ is either in $S$ or adjacent to some vertex in $S$, and no two vertices in $S$ are adjacent. Consider graphs of $n$ nodes that are dense, i.e., there are $m$ edges, where $m \ge n^{1+\epsilon}$, for some constant $\epsilon>0$.

Update: As pointed out in the comments, one can take $n/2$ isolated vertices and then any dense graph of high $\ge 5$ on the remaining $n/2$ vertices. However, I'm more interested in regular graphs where every node has the same degree. I've updated my question is as follows:

Does there exist a family of regular dense graphs of girth $\ge 5$ where every maximal independent set has a size of at least $\Omega(n)$?

Note that the girth $\ge 5$ condition rules out obvious candidates such as the complete bipartite graph which has girth $4$.

  • 1
    $\begingroup$ You'll want to add the condition that no two vertices in $S$ are adjacent. $\endgroup$ – Carl-Fredrik Nyberg Brodda Apr 17 at 13:32
  • 1
    $\begingroup$ Couldn't you just take the disjoint union of $n/2$ isolated vertices and any dense graph of girth at least $5$ on $n/2$ vertices? $\endgroup$ – Florian Lehner Apr 19 at 16:24
  • $\begingroup$ @FlorianLehner: you're right, but actually I'm more interested in regular graphs. I've updated the question. $\endgroup$ – wandering_lambda Apr 20 at 2:01
  • 1
    $\begingroup$ I’m inclined to believe the answer is no they do not exist. A natural candidate would be the incidence graph of a projective plane. This is a regular girth 6 bipartite graph with $n$ vertices, roughly $n^{3/2}$ edges, but its independence domination number (the parameter you care about) is only order $\sqrt{n}$. semion.io/doc/domination-in-designs $\endgroup$ – Pat Devlin Apr 23 at 13:20

No, the object you’re looking for does not exist.

A result of Harutyunyan, Horn, and Verstraete (see Theorem 4.15 of this survey) states the following

Theorem: There is a constant $c > 0$ such that every $d$-regular graph $G$ on $n$ vertices of girth at least 5 satisfies $i(G) \leq \dfrac{n(\log(d)+c)}{d}$.

Here, $i(G)$ is the independence domination number, which is the size of the smallest maximal independent set.

Setting $m=n^{1+\varepsilon}$, this bound gives $i(G) \leq O(n^{1-\varepsilon} \log(n)) = o(n)$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.