- Tytuł:
- A note on the p-domination number of trees
- Autorzy:
-
Lu, Y.
Hou, X.
Xu, J.-M. - Powiązania:
- https://bibliotekanauki.pl/articles/255183.pdf
- Data publikacji:
- 2009
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
p-domination number
trees - Opis:
- 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.
- Źródło:
-
Opuscula Mathematica; 2009, 29, 2; 157-164
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł