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.
- 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
- Received: 2009-07-16.
- Revised: 2010-01-07.
- Accepted: 2010-01-09.
