×

An algorithm to find two distance domination parameters in a graph. (English) Zbl 0848.05040

A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called total \(n\)-dominating, if for each \(x \in V(G)\) there exists a vertex \(y \in D\) distinct from \(x\) such that the distance between \(x\) and \(y\) is less than or equal to \(n\). A subset \(S\) of \(V(G)\) is called \(n\)-independent, if the distance between any two vertices of \(S\) is at least \(n + 1\). The minimum number of vertices of a total \(n\)-dominating set in \(G\) is the total \(n\)-domination number \(\gamma_n' (G)\), the minimum number of vertices of a maximal (with respect to set inclusion) \(n\)-independent set in \(G\) is the \(n\)-independence number \(i_n (G)\) of \(G\). The paper presents an algorithm for finding a total \(n\)-dominating set and a maximal \(n\)-independent set in a graph \(G\) with \(p \geq 2n + 1\) vertices. For such graphs the inequality \(i_n (G) + n \gamma_n' (G) \leq p\) is proved.

MSC:

05C35 Extremal problems in graph theory
05C12 Distance in graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allan, R. B.; Laskar, R.; Hedetniemi, S. T., A note on total domination, Discrete Math., 49, 7-13 (1984) · Zbl 0576.05028
[2] Bascó, G.; Tuza, Z., Dominating cliques in \(P_5\)-free graphs, Periodi. Math. Hungar., 21, 303-308 (1990) · Zbl 0746.05065
[3] Bascó, G.; Tuza, Z., A characterization of graphs without long induced paths, J. Graph Theory, 14, 455-464 (1990) · Zbl 0717.05044
[4] L. Beineke and M.A. Henning, Some extremal results on independent distance domination in graphs, Ars. Combin., to appear.; L. Beineke and M.A. Henning, Some extremal results on independent distance domination in graphs, Ars. Combin., to appear. · Zbl 0805.05040
[5] Bondy, J. A.; Fan, G., A sufficient condition for dominating cycles, Discrete Math., 76, 205-208 (1987) · Zbl 0634.05045
[6] Chang, G. J., \(k\)-domination and graph covering problems, (Ph.D Thesis (1982), School of OR and IE, Cornell University: School of OR and IE, Cornell University Ithaca, NY)
[7] Chang, G. J.; Nemhauser, G. L., \(R\)-domination of block graphs, Oper. Res. Lett., 1, 6, 214-218 (1982) · Zbl 0498.90023
[8] 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)
[9] Chang, G. J.; Nemhauser, G. L., The \(k\)-domination and \(k\)-stability problems on sunfree chordal graphs, SIAM J. Algebraic Discrete Methods, 5, 3, 332-345 (1984) · Zbl 0576.05054
[10] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1986), Wadsworth and Brooks/Cole: Wadsworth and Brooks/Cole Monterey, CA · Zbl 0666.05001
[11] Fraisse, P., A note on distance dominating cycles, Discrete Math., 71, 1, 89-92 (1988) · Zbl 0642.05031
[12] G. Fricke, S.T. Hedetniemi and M.A. Henning, Distance independent domination in graphs, Ars Combin., to appear.; G. Fricke, S.T. Hedetniemi and M.A. Henning, Distance independent domination in graphs, Ars Combin., to appear. · Zbl 0844.05059
[13] G. Fricke, S.T. Hedetniemi and M.A. Henning, Asymptotic results on distance independent domination in graphs, J. Combin. Math. Combin. Comput., to appear.; G. Fricke, S.T. Hedetniemi and M.A. Henning, Asymptotic results on distance independent domination in graphs, J. Combin. Math. Combin. Comput., to appear. · Zbl 0821.05019
[14] Hattingh, J. H.; Henning, M. A., A characterization of block graphs that are well-\(k\)-dominated, J. Combin. Math. Combin. Comput., 13, 33-38 (1993) · Zbl 0779.05037
[15] Hattingh, J. H.; Henning, M. A., The ratio of the distance irredundance and domination numbers, J. Graph Theory, 18, 1-9 (1994) · Zbl 0789.05047
[16] Henning, M. A.; System, O. R.Oellermann; Swart, H. C., Bounds on distance domination parameters, J. Combin. Inform. System Sci., 16, 11-18 (1991) · Zbl 0766.05040
[17] Henning, M. A.; Oellermann, O. R.; Swart, H. C., Relationships between distance domination parameters, Math. Pannon., 5, 1, 69-79 (1994) · Zbl 0801.05038
[18] M.A. Henning, O.R. Oellermann and H.C. Swart, Relating pairs of distance domination parameters, in J. Combin. Math. Combin. Comput, to appear.; M.A. Henning, O.R. Oellermann and H.C. Swart, Relating pairs of distance domination parameters, in J. Combin. Math. Combin. Comput, to appear. · Zbl 0830.05039
[19] M.A. Henning, O.R. Oellermann and H.C. Swart, Distance domination critical graphs, J. Combin. Sci., Inform. System to appear.; M.A. Henning, O.R. Oellermann and H.C. Swart, Distance domination critical graphs, J. Combin. Sci., Inform. System to appear. · Zbl 1035.05064
[20] M.A. Henning, O.R. Oellermann and H.C. Swart, The diversity of domination, Discrete Math., to appear.; M.A. Henning, O.R. Oellermann and H.C. Swart, The diversity of domination, Discrete Math., to appear. · Zbl 0870.05034
[21] Meir, A.; Moon, J. W., Relations between packing and covering numbers of a tree, Pacific J. Math., 61, 225-233 (1975) · Zbl 0315.05102
[22] Mo, Z.; Williams, K., \((r, s)\)-domination in graphs and directed graphs, Ars. Combin., 29, 129-141 (1990) · Zbl 0729.05026
[23] Slater, P. J., \(R\)-domination in graphs, J. A.C.M., 23, 446-450 (1976) · Zbl 0349.05120
[24] Topp, J.; Volkmann, L., On packing and covering numbers of graphs, Discrete Math., 96, 229-238 (1991) · Zbl 0759.05077
[25] He, Xin; Yesha, Y., Efficient parallel algorithms for \(r\)-dominating set and \(p\)-center problems on trees, Algorithmica, 5, 129-145 (1990) · Zbl 0686.68054
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.