A remark on the (2,2)-domination number
Torsten Korneffel ; Dirk Meierling ; Lutz Volkmann
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 361-366 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270462 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1411,
     author = {Torsten Korneffel and Dirk Meierling and Lutz Volkmann},
     title = {A remark on the (2,2)-domination number},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {361-366},
     zbl = {1156.05044},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1411}
}

Torsten Korneffel; Dirk Meierling; Lutz Volkmann. A remark on the (2,2)-domination number. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 361-366. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1411/

[000] [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. | Zbl 0815.05036

[001] [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. | Zbl 0664.05053

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

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

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

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