Opuscula Math. 30, no. 2 (2010), 179-191
http://dx.doi.org/10.7494/OpMath.2010.30.2.179

Opuscula Mathematica

# Domination hypergraphs of certain digraphs

Martin Sonntag
Hanns-Martin Teichert

Abstract. If $$D = (V,A)$$ is a digraph, its domination hypergraph $$\mathcal{DH}(D) = (V,\mathcal{E})$$ has the vertex set $$V$$ and $$e \subseteq V$$ is an edge of $$\mathcal{DH}(D)$$ if and only if $$e$$ is a minimal dominating set of $$D$$. We investigate domination hypergraphs of special classes of digraphs, namely tournaments, paths and cycles. Finally, using a special decomposition/composition method we construct edge sets of domination hypergraphs of certain digraphs.

Keywords: hypergraph, dominating set, directed graph.

Mathematics Subject Classification: 05C65, 05C20.

Full text (pdf)