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

$\endgroup$
2
  • 1
    $\begingroup$ $G=(\mathbb N,\le)$ ? $\endgroup$
    – saf
    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$ Jan 30, 2017 at 16:10

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.