A note on the p-domination number of trees

• Autorzy: Lu Y. , Hou X. , Xu J.-M.
• Języki publikacji: EN

Abstrakty

EN

Let p be a positive integer and G = (V (G), E(G)) a graph. A p-dominating set of G is a subset S of V (G) such that every vertex not in S is dominated by at least p vertices in S. The p-domination number ϒp(G) is the minimum cardinality among the p-dominating sets of G. Let T be a tree with order n ≥ 2 and p ≥ 2 a positive integer. A vertex of V (T) is a p-leaf if it has degree at most p - 1, while a p-support vertex is a vertex of degree at least p adjacent to a p-leaf. In this note, we show that ϒp(T) ≥ (n + /Lp(T)/ - /Sp(T)/)/2, where Lp(T) and Sp(T) are the sets of p-leaves and p-support vertices of T, respectively. Moreover, we characterize all trees attaining this lower bound.

Słowa kluczowe

EN

p-domination number; trees

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2009
• Tom: Vol. 29, no. 2
• Strony: 157--164
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Lu Y.

autor

Hou X.

autor

Xu J.-M.

• University of Science and Technology of China Department of Mathematics Hefei, Anhui, 230026, China,

Bibliografia

• [1] M. Blidia, M. Chellali, L. Volkmann, Some bounds on the p-domination number in trees, Discrete Math. 306 (2006), 2031–2037.
• [2] G. Chartrant, L. Lesniak, Graphs & Digraphs, 3rd ed., Chapman & Hall, London, 1996.
• [3] M. Chellali, Bounds on the 2-domination number in cactus graphs, Opuscula Math. 26 (2006), 5–11.
• [4] J.F. Fink, M.S. Jacobson, n-Domination in graphs, [in:] Y.Alavi, A.J.Schwenk (Eds.), Graph Theory with Applications to Algorithms and Computer Science, Wiley, New York, 1985, 283–300.
• [5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of domination in graphs, New York, Marcel Deliker, 1998.
• [6] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs: Advanced Topics, New York, Marcel Deliker, 1998.
• [7] M. Lemanska, Lower bound on the domination number of a tree, Discuss. Math. Graph Theory 24(2) (2004), 165–169.
• [8] L.Volkmann, Some remarks on lower bounds on the p-domination number in trees, J. Combin. Math. Combin. Comput. 61 (2007), 159–167.