0
$\begingroup$

Suppose that $G=(V,E)$ is a simple, undirected graph. We say that $D\subseteq V$ is dominating if for all $v\in V\setminus D$ there is $d\in D$ such that $\{v,d\}\in E$. We say $D$ is minimal dominating if for all $d\in D$ we have that $D\setminus\{d\}$ is no longer dominating. There are graphs that do not have minimal dominating sets.

We call $G=(V,E)$ flat if for all $v\in V$ the neighborhood $N_G(v)=\{w\in V:\{v,w\}\in E\}$ is finite.

If $G=(V,E)$ is a flat graph, does $G$ necessarily contain a minimal dominating set? Is it even the case that every dominating set contains a minimal dominating set? (Only answering the first question is sufficient for acceptance, but it would be lovely to have the answer to both questions.)

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

For flat graphs, dominating sets satisfy Zorn's condition: the intersection of a chain of dominating sets $D:=\cap D_\alpha$ is dominating. Indeed, for any vertex $v$ the finite set $\{v\cup N(v)\}$ has non-empty intersection with every $D_\alpha$, thus this finite non-empty intersection stabilizes and its limit is contained in $D$.

So, the answer is positive by Zorn lemma.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Yep. Instead of Zorn's lemma, it follows even more directly from Tukey's lemma. Minimal dominating sets for $G$ are just the complements of maximal independent sets for the hypergraph whose edges are the closed neighborhoods $N_G[v]=\{v\}\cup N_G(v)$. $\endgroup$
    – bof
    Commented Aug 18, 2023 at 7:26

You must log in to answer this question.

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