A note on a conjecture on niche hypergraphs

Kaemawichanurat, Pawaton ; Jiarasuksakun, Thiradet

Czechoslovak Mathematical Journal, Tome 69 (2019) no. 1, pp. 93-97

Résumé

For a digraph $D$, the niche hypergraph $N\mathcal {H}(D)$ of $D$ is the hypergraph having the same set of vertices as $D$ and the set of hyperedges $E(N\mathcal {H}(D)) = \{e \subseteq V(D) \colon |e| \geq 2$ and there exists a vertex $v$ such that $e = N^{-}_{D}(v)$ or $e = N^{+}_{D}(v)\}$. A digraph is said to be acyclic if it has no directed cycle as a subdigraph. For a given hypergraph $\mathcal {H}$, the niche number $\hat {n}(\mathcal {H})$ is the smallest integer such that $\mathcal {H}$ together with $\hat {n}(\mathcal {H})$ isolated vertices is the niche hypergraph of an acyclic digraph. C. Garske, M. Sonntag and H. M. Teichert (2016) conjectured that for a linear hypercycle $\mathcal {C}_{m}$, $m \geq 2$, if $\min \{|e| \colon e \in E(\mathcal {C}_{m})\} \geq 3$, then $\hat {n}(\mathcal {C}_{m}) = 0$. In this paper, we prove that this conjecture is true.

Détail

DOI : 10.21136/CMJ.2018.0182-17

Classification : 05C65
Keywords: niche hypergraph; digraph; linear hypercycle