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)

• Martin Sonntag
• Freiberg University of Mining and Technology, Faculty of Mathematics and Computer Science, Prüferstr. 1, D–09596 Freiberg, Germany
• Hanns-Martin Teichert
• University of Lübeck, Institute of Mathematics, Wallstr. 40, D–23560 Lübeck, Germany
• Revised: 2010-01-07.
• Accepted: 2010-01-09.