Geodesic
A remark on the (2,2)-domination number
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 2, pp. 361-366 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: domination, distance domination number, p-domination number 
@article{DMGT_2008_28_2_a10,
     author = {Korneffel, Torsten and Meierling, Dirk and Volkmann, Lutz},
     title = {A remark on the (2,2)-domination number},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {361--366},
     year = {2008},
     volume = {28},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a10/}
}
TY  - JOUR
AU  - Korneffel, Torsten
AU  - Meierling, Dirk
AU  - Volkmann, Lutz
TI  - A remark on the (2,2)-domination number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2008
SP  - 361
EP  - 366
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a10/
LA  - en
ID  - DMGT_2008_28_2_a10
ER  - 
%0 Journal Article
%A Korneffel, Torsten
%A Meierling, Dirk
%A Volkmann, Lutz
%T A remark on the (2,2)-domination number
%J Discussiones Mathematicae. Graph Theory
%D 2008
%P 361-366
%V 28
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a10/
%G en
%F DMGT_2008_28_2_a10
Korneffel, Torsten; Meierling, Dirk; Volkmann, Lutz. A remark on the (2,2)-domination number. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 2, pp. 361-366. http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a10/

[1] T.J. Bean, M.A. Henning and H.C. Swart, On the integrity of distance domination in graphs, Australas. J. Combin. 10 (1994) 29-43.

[2] E.J. Cockayne, B. Gamble and B. Shepherd, An upper bound for the k-domination number of a graph, J. Graph Theory 9 (1985) 101-102, doi: 10.1002/jgt.3190090414.

[3] M. Fischermann and L. Volkmann, A remark on a conjecture for the (k,p)-domination number, Util. Math. 67 (2005) 223-227.

[4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998).

[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcel Dekker, Inc., New York, 1998).

[6] A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225-233.