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

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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