Temat: p-domination number - Katalog OPAC zbiorów

Skocz do pozycji: 1.

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ł

Skocz do pozycji: 2.

Tytuł:: A remark on the (2,2)-domination number
Autorzy:: Korneffel, Torsten
Meierling, Dirk
Volkmann, Lutz
Powiązania:: https://bibliotekanauki.pl/articles/743033.pdf
Data publikacji:: 2008
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: domination
distance domination number
p-domination number
Opis:: A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter $γ_{k,p}(G)$ denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that $γ_{k,p}(G) ≤ (p/(p+k))n(G)$ for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture for all integers k and p for the case that p is a multiple of k. In this paper we show that $γ_{2,2}(G) ≤ (n(G)+1)/2$ for all connected graphs G and characterize all connected graphs with $γ_{2,2} = (n+1)/2$. This means that for k = p = 2 we characterize all connected graphs for which the conjecture is true without the precondition that δ₂ ≥ 3.
Źródło:: Discussiones Mathematicae Graph Theory; 2008, 28, 2; 361-366
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: On the p-domination number of cactus graphs
Autorzy:: Blidia, Mostafa
Chellali, Mustapha
Volkmann, Lutz
Powiązania:: https://bibliotekanauki.pl/articles/744381.pdf
Data publikacji:: 2005
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: p-domination number
cactus graphs
Opis:: Let p be a positive integer and G = (V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times. The minimum cardinality of a p-dominating set a of G is the p-domination number γₚ(G). It is proved for a cactus graph G that γₚ(G) ⩽ (|V| + |Lₚ(G)| + c(G))/2, for every positive integer p ⩾ 2, where Lₚ(G) is the set of vertices of G of degree at most p-1 and c(G) is the number of odd cycles in G.
Źródło:: Discussiones Mathematicae Graph Theory; 2005, 25, 3; 355-361
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja