Domination hypergraphs of certain digraphs

• Autorzy: Sonntag M. , Teichert H. M.
• Języki publikacji: EN

Abstrakty

EN

If D = (V,A) is a digraph, its domination hypergraph DH(D) = (V, E) has the vertex set V and e ⊆ V is an edge of 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.

Słowa kluczowe

EN

hypergraph; dominating set; directed graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2010
• Tom: Vol. 30, no. 2
• Strony: 179--191
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Sonntag M.

autor

Teichert H. M.

• Freiberg University of Mining and Technology Faculty of Mathematics and Computer Science Prüferstr. 1, D-09596 Freiberg, Germany,

Bibliografia

• [1] C. Berge, Hypergraphs, North Holland, Amsterdam-New York-Oxford-Tokyo, 1989.
• [2] H.H. Cho, S.-R. Kim, J.R. Lundgren, Domination graphs of regular tournaments, Discrete Mathematics 252 (2002), 57–71.
• [3] D.C. Fisher, D. Guichard, J.R. Lundgren, S.K. Merz, K.B. Reid, Domination graphs with nontrivial components, Graphs and Combinatorics 17 (2001), 227–236.
• [4] D.C. Fisher, J.R. Lundgren, D. Guichard, S.K. Merz, K.B. Reid, Domination graphs of tournaments with isolated vertices, Ars Combinatoria 66 (2003), 299–311.
• [5] D.C. Fisher, J.R. Lundgren, S.K. Merz, K.B. Reid, Domination graphs of tournaments and digraphs, Congressus Numerantium 108 (1995), 97–107.
• [6] D.C. Fisher, J.R. Lundgren, S.K. Merz, K.B. Reid, The domination and competition graphs of a tournament, Journal of Graph Theory 29 (1998), 103–110.
• [7] D.C. Fisher, J.R. Lundgren, S.K. Merz, K.B. Reid, Connected domination graphs of tournaments, J. Combin. Math. Combin. Comput. 31 (1999), 169–176.
• [8] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds.), Fundamentals of domination in graphs, Marcel Dekker, New York-Basel, 1998.
• [9] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds.), Domination in graphs – Advanced topics, Marcel Dekker, New York-Basel-Hong Kong, 1998.
• [10] P. McKenna, M. Morton, J. Sneddon, New domination conditions for tournaments, Australasian J. of Combin. 26 (2002), 171–182.
• [11] K.B. Reid, Tournaments: scores, kings, generalizations and special topics, Congressus Numerantium 115 (1996), 171–211.
• [12] C. Wartner, Konkurrenzgraphen und Dominanzhypergraphen von Digraphen, Bachelor Thesis, Technische Universität Bergakademie Freiberg, 2006.