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$ Apr 17 '20 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$ Apr 19 '20 at 16:24
  • $\begingroup$ @FlorianLehner: you're right, but actually I'm more interested in regular graphs. I've updated the question. $\endgroup$ Apr 20 '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 '20 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)$.


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.