- 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ł