# Dense graphs where every maximal independent set is large

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

• You'll want to add the condition that no two vertices in $S$ are adjacent. – Carl-Fredrik Nyberg Brodda Apr 17 at 13:32
• 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? – Florian Lehner Apr 19 at 16:24
• @FlorianLehner: you're right, but actually I'm more interested in regular graphs. I've updated the question. – wandering_lambda Apr 20 at 2:01
• 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 – Pat Devlin Apr 23 at 13:20

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)$$.