Discussiones Mathematicae Graph Theory 28(2) (2008) 361-366
doi: 10.7151/dmgt.1411

[BIBTex] [PDF] [PS]


Torsten Korneffel, Dirk Meierling and Lutz Volkmann

Lehrstuhl II für Mathematik
RWTH Aachen University, 52056 Aachen, Germany
e-mail: {korneffe,meierling,volkm}@math2.rwth-aachen.de


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 δk(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 δ2 ≥ 3.

Keywords: domination, distance domination number, p-domination number.

2000 Mathematics Subject Classification: 05C69.


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

Received 2 May 2007
Revised 25 March 2008
Accepted 25 March 2008