# A remark on the (2,2)-domination number

Torsten Korneffel; Dirk Meierling; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2008)

- Volume: 28, Issue: 2, page 361-366
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topTorsten Korneffel, Dirk Meierling, and Lutz Volkmann. "A remark on the (2,2)-domination number." Discussiones Mathematicae Graph Theory 28.2 (2008): 361-366. <http://eudml.org/doc/270462>.

@article{TorstenKorneffel2008,

abstract = {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.},

author = {Torsten Korneffel, Dirk Meierling, Lutz Volkmann},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {domination; distance domination number; p-domination number; -domination number},

language = {eng},

number = {2},

pages = {361-366},

title = {A remark on the (2,2)-domination number},

url = {http://eudml.org/doc/270462},

volume = {28},

year = {2008},

}

TY - JOUR

AU - Torsten Korneffel

AU - Dirk Meierling

AU - Lutz Volkmann

TI - A remark on the (2,2)-domination number

JO - Discussiones Mathematicae Graph Theory

PY - 2008

VL - 28

IS - 2

SP - 361

EP - 366

AB - 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.

LA - eng

KW - domination; distance domination number; p-domination number; -domination number

UR - http://eudml.org/doc/270462

ER -

## References

top- [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. Zbl0815.05036
- [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. Zbl0664.05053
- [3] M. Fischermann and L. Volkmann, A remark on a conjecture for the (k,p)-domination number, Util. Math. 67 (2005) 223-227. Zbl1077.05074
- [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
- [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcel Dekker, Inc., New York, 1998). Zbl0883.00011
- [6] A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225-233. Zbl0315.05102