Henning, Michael A.; Oellermann, Ortrud R.; Swart, Henda C. The diversity of domination. (English) Zbl 0870.05034 Discrete Math. 161, No. 1-3, 161-173 (1996). Summary: For any graph \(G\) and a set \({\mathcal H}\) of graphs, two distinct vertices of \(G\) are said to be \({\mathcal H}\)-adjacent if they are contained in a subgraph of \(G\) which is isomorphic to a member of \({\mathcal H}\). A set \(S\) of vertices of \(G\) is an \({\mathcal H}\)-dominating set (total \({\mathcal H}\)-dominating set) of \(G\) if every vertex in \(V(G)-S\) \((V(G)\), respectively) is \({\mathcal H}\)-adjacent to a vertex in \(S\). An \({\mathcal H}\)-domianting set of \(G\) in which no two vertices are \({\mathcal H}\)-adjacent in \(G\) is an \({\mathcal H}\)-independent dominating set of \(G\). The minimum cardinality of an \({\mathcal H}\)-dominating set, total \({\mathcal H}\)-dominating set and \({\mathcal H}\)-independent dominating set of \(G\) is known as the \({\mathcal H}\)-domination number, total \({\mathcal H}\)-domination number, and \({\mathcal H}\)-independent dominating number, of \(G\), denoted, respectively, by \(\gamma_{\mathcal H}(G)\), \(\gamma_{\mathcal H}^t(G)\), and \(i_{\mathcal H}(G)\). We survey the applications and bounds obtained for the above domination parameters if \({\mathcal H}=\{K_n\}\) or \({\mathcal H}=\{P_i\mid 2\leq i\leq n\}\), for an integer \(n\geq 2\). Cited in 9 Documents MSC: 05C35 Extremal problems in graph theory Keywords:dominating set; domination PDFBibTeX XMLCite \textit{M. A. Henning} et al., Discrete Math. 161, No. 1--3, 161--173 (1996; Zbl 0870.05034) Full Text: DOI References: [1] Allan, R. B.; Laskar, R., On domination and some related topics in graph theory, (Proc. 9th Southeastern Conf. on Graph Theory, Combinatorics and Computing, Utilitas Mathematicae. Proc. 9th Southeastern Conf. on Graph Theory, Combinatorics and Computing, Utilitas Mathematicae, Winnipeg (1978)), 43-56 [2] Allan, R. B.; Laskar, R.; Hederniemi, S., A note on total domination, Discrete Math., 49, 7-13 (1984) · Zbl 0576.05028 [3] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland London · Zbl 0483.05029 [4] Bollobás, B.; Cockayne, E. J., Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory, 3, 241-249 (1979) · Zbl 0418.05049 [5] Booth, K. S.; Johnson, J. H., Dominating sets in chordal graphs, SIAM J. Comput., 11, 191-199 (1982) · Zbl 0485.05055 [6] Chang, G. J.; Nemhauser, G. L., The \(k\)-domination and \(k\)-stability problem on graphs, (Tech. Report 540 (1982), School of Operations Res. and Industrial Eng., Cornell Univ) [7] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1986), Wadsworth and Brooks/Cole: Wadsworth and Brooks/Cole Monterey, CA · Zbl 0666.05001 [8] Cockayne, E. J.; Dawes, R. M.; Hedetniemi, S. T., Total domination in graphs, Networks, 10, 211-219 (1980) · Zbl 0447.05039 [9] Cockayne, E. J.; Goodman, S.; Hedetniemi, S. T., A linear algorithm for the domination number of a tree, Inform. Processing Lett., 4, 41-44 (1975) · Zbl 0311.68024 [10] Cockayne, E. J.; Hedetmiemi, S. T., Towards a theory of domination in graphs, Networks, 7, 247-261 (1977) · Zbl 0384.05051 [11] de Jaenisch, C. F., Applications de l’Analyse Mathematique au Ju des Echoes (1862), Petrogard [12] Farber, M., Applications of linear programming duality to problems involving independence and domination, (TR 81-13 (1981), Department of Computer Science, Simon Fraser University: Department of Computer Science, Simon Fraser University Canada) [13] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 [14] Henning, M. A., Generalized adjacency in graphs, (Ph.D. Thesis (1989), University of Natal) [15] Henning, M. A.; Oellermann, O. R.; Swart, H. C., Bounds on distance domination parameters, J. Combin. Inform. System Sci., 16, 11-18 (1991) · Zbl 0766.05040 [16] M.A. Henning, O.R. Oellermann and H.C. Swart, Distance domination critical graphs. J. Combin. Inform. System Sci., to appear.; M.A. Henning, O.R. Oellermann and H.C. Swart, Distance domination critical graphs. J. Combin. Inform. System Sci., to appear. · Zbl 1035.05064 [17] Henning, M. A.; Oellermann, O. R.; Swart, H. C., Relationships between distance domination parameters, Math. Pannonica, 5, 69-79 (1994) · Zbl 0801.05038 [18] Henning, M. A.; Oellermann, O. R.; Swart, H. C., Relating pairs of distance domination parameters, J. Combin. Math. Combin. Comput., 18, 233-244 (1995) · Zbl 0830.05039 [19] Henning, M. A.; Swart, H. C., Bounds on a generalized total domination parameter, J. Combin. Math. Combin. Comput., 6, 143-153 (1989) · Zbl 0692.05057 [20] Henning, M. A.; Swart, H. C., Bounds on a generalized domination parameter, Quaestiones Math., 13, 237-253 (1990) · Zbl 0709.05029 [21] Henning, M. A.; Swart, H. C., Bounds relating generalized domination parameters, Discrete Math., 120, 93-105 (1993) · Zbl 0781.05031 [22] Jaeger, F.; Payan, C., Relations du type Nordhaus-Gaddum pour le nombre d’absorption d’un graphe simple, C.R. Acad. Sci. Ser. A, 274, 728-730 (1972) · Zbl 0226.05121 [23] Kelleher, L. L., Domination in graphs and its application to social network theory, (Ph.D. Thesis (1987), Northeastern University) [24] Lichtenstein, D., Planar satisfiability and its uses, SIAM J. Comput. (1977) [25] Nordhaus, E. A.; Gaddum, J. W., On complementary graphs, Amer. Math. Monthly, 63, 175-177 (1956) · Zbl 0070.18503 [26] Ore, O., Theory of Graphs (1962), Amer. Math. Soc: Amer. Math. Soc Providence This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.