5
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You'll want to add the condition that no two vertices in $S$ are adjacent. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented Apr 17, 2020 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
    Commented Apr 19, 2020 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
    Commented Apr 20, 2020 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
    Commented Apr 23, 2020 at 13:20

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .