2
$\begingroup$

Let $G=(V,E)$ be any simple, undirected graph. A dominating set is a set $D\subseteq V$ such that for all $v\in V\setminus D$ there is $d\in D$ such that $\{v,d\}\in E$.

Is there an infinite graph $G=(V,E)$ such that there is a dominating subset $D\subseteq V$ such that for any dominating subset $D_1\subseteq D$ there is a dominating subset $D_2\subseteq D_1$ with $D_2\neq D_1$?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ $G=(\mathbb N,\le)$ ? $\endgroup$
    – saf
    Commented Jan 30, 2017 at 16:02
  • 1
    $\begingroup$ @saf That doesn't work, since any singleton is dominating, but the empty set is not. $\endgroup$
    – Joel David Hamkins
    Commented Jan 30, 2017 at 16:10

1 Answer 1

Reset to default
4
$\begingroup$

Let $V(G)$ be the set of non-empty subsets of $\mathbb N$ and join two sets by an edge whenever they intersect. Let $D$ be the set of initial segments of $\mathbb N$. Then subsets of $D$ are dominating if and only if they are infinite.

Improve this answer
$\endgroup$

You must log in to answer this question.

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