4
$\begingroup$

Let $H=(V,E)$ be a hypergraph. We say that $H$ is thin if for every $v\in V$ the set $E_v=\{e\in E:v\in e\}$ is finite.

A subset $D\subseteq V$ is dominating if $\bigcup \{e\in E:e\cap D \neq \emptyset\} = V$.

Question. Does every thin hypergraph $H=(V,E)$ with $\bigcup E = V$ have a minimal dominating set $D_0\subseteq V$? ($D_0\subseteq V$ is minimal dominating if for all $d\in D_0$ the set $D_0\setminus \{d\}$ is no longer dominating.)

Improve this question
$\endgroup$
2
  • $\begingroup$ In the definition of a do inating set, should the union be really $V$ but not $E$? $\endgroup$
    – Ilya Bogdanov
    Commented Sep 24 at 10:31
  • $\begingroup$ I don't think so, @IlyaBogdanov, because we take the union over some edges $e\in E$, and this union gives a subset of $V$ -> which we require to equal $V$. Does that make sense? $\endgroup$
    – Dominic van der Zypen
    Commented Sep 25 at 6:36

1 Answer 1

Reset to default
5
$\begingroup$

The answer seems to be yes.

Any maximal independent(=no two its vertices share an edge) set is a minimal dominating set. It exists by Zorn’s lemma.

The condition on finite degrees is not used…

======================

This is a previous (wrong) answer, as I misread the definition of a dominating set.

Choose $V=\{1,2,\dots\}$ and let the edges be $e_i=\{i,i+1,\dots\}$. The dominating sets are precisely infinite ones.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Isn't that dominated by any singleton, because all singletons have non-empty intersection with $e_1 = V$? $\endgroup$
    – Peter Taylor
    Commented Sep 24 at 9:57
  • $\begingroup$ @PeterTaylor you need all edges to be pierced by the dominating set. So the dominating set should contain arbitrarily large numbers… $\endgroup$
    – Ilya Bogdanov
    Commented Sep 24 at 10:01
  • $\begingroup$ Are you using a different definition of dominating? I don't see how $\bigcup \{e\in E:e\cap D \neq \emptyset\} = V$ requires $\{e\in E:e\cap D \neq \emptyset\} = E$ as you claim. $\endgroup$
    – Peter Taylor
    Commented Sep 24 at 10:15
  • $\begingroup$ Eh… Seems that I really misread the question, but then this is really not the usual definition… $\endgroup$
    – Ilya Bogdanov
    Commented Sep 24 at 10:30
  • 1
    $\begingroup$ It seems to be equivalent to e.g. definition 1.2 of Acharya, B. D. (2007). Domination in hypergraphs. AKCE International Journal of Graphs and Combinatorics, 4(2), 117-126. $\endgroup$
    – Peter Taylor
    Commented Sep 24 at 10:53

You must log in to answer this question.

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