×

Some bounds on the \(p\)-domination number in trees. (English) Zbl 1100.05069

For a positive integer \(p\) and a graph \(G=(V,E)\), a subset \(S\) of \(V\) is called a \(p\)-dominating set, if every vertex of \(V\setminus S\) is dominated at least \(p\) times; and \(S\) is called a \(p\)-dependent set if the subgraph of \(G\) induced by the vertices of \(S\) has maximum degree at most \(p-1\). The maximum cardinality of a \(p\)-dominating set of \(G\) is called the \(p\)-domination number \(\gamma_p(G)\), and the maximum cardinality of a \(p\)-dependent set of \(G\) is called the \(p\)-dependence number \(\beta_p(G)\). The paper shows that for \(p\geq 2 \) and a bipartite graph \(G\), \(\gamma_p(G)\) is bounded above by \((| V| +| Y_p| )/2\), where \(Y_p\) is the set of vertices in \(G\) of degree at most \(p-1\); and for every tree \(T\) \(\gamma_p(T)\) is bounded below by \(\beta_{p-1} (T)\). Trees achieving equality in both bounds are characterized.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blidia, M.; Chellali, M.; Favaron, O., Independence and 2-domination in trees, Austral. J. Combin., 33, 317-327 (2005) · Zbl 1081.05081
[2] Caro, Y.; Roditty, Y., A note on the \(k\)-domination number of a graph, Internat. J. Math. Sci., 13, 205-206 (1990) · Zbl 0706.05033
[3] Chartrand, G.; Lesniak, L., Graphs & Digraphs (1996), Chapman & Hall: Chapman & Hall London · Zbl 0890.05001
[4] Favaron, O., On a conjecture of Fink and Jacobson concerning \(k\)-domination and \(k\)-dependence, J. Combin. Theory Ser. B, 39, 101-102 (1985) · Zbl 0583.05049
[5] Fink, J. F.; Jacobson, M. S., \(n\)-Domination in graphs, (Alavi, Y.; Schwenk, A. J., Graph Theory with Applications to Algorithms and Computer Science (1985), Wiley: Wiley New York), 283-300
[6] Fink, J. F.; Jacobson, M. S., On \(n\)-domination, \(n\)-dependence and forbidden subgraphs, Graph Theory with Applications to Algorithms and Computer Science (1985), Wiley: Wiley New York, pp. 301-312
[7] Gallai, T., Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 2, 133-138 (1959) · Zbl 0094.36105
[8] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002
[9] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.; T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998. · Zbl 0883.00011
[10] König, D., Graphs and matrices, Mat. Fiz. Lapok, 38, 116-119 (1931), (in Hungarian) · JFM 57.1340.04
[11] Stracke, C.; Volkmann, L., A new domination conception, J. Graph Theory, 17, 13, 315-323 (1993) · Zbl 0777.05074
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.