# Efficient (j,k)-domination

Robert R. Rubalcaba; Peter J. Slater

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 3, page 409-423
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRobert R. Rubalcaba, and Peter J. Slater. "Efficient (j,k)-domination." Discussiones Mathematicae Graph Theory 27.3 (2007): 409-423. <http://eudml.org/doc/270577>.

@article{RobertR2007,

abstract = {A dominating set S of a graph G is called efficient if |N[v]∩ S| = 1 for every vertex v ∈ V(G). That is, a dominating set S is efficient if and only if every vertex is dominated exactly once. In this paper, we investigate efficient multiple domination. There are several types of multiple domination defined in the literature: k-tuple domination, \{k\}-domination, and k-domination. We investigate efficient versions of the first two as well as a new type of multiple domination.},

author = {Robert R. Rubalcaba, Peter J. Slater},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {efficient domination; multiple domination},

language = {eng},

number = {3},

pages = {409-423},

title = {Efficient (j,k)-domination},

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

volume = {27},

year = {2007},

}

TY - JOUR

AU - Robert R. Rubalcaba

AU - Peter J. Slater

TI - Efficient (j,k)-domination

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 3

SP - 409

EP - 423

AB - A dominating set S of a graph G is called efficient if |N[v]∩ S| = 1 for every vertex v ∈ V(G). That is, a dominating set S is efficient if and only if every vertex is dominated exactly once. In this paper, we investigate efficient multiple domination. There are several types of multiple domination defined in the literature: k-tuple domination, {k}-domination, and k-domination. We investigate efficient versions of the first two as well as a new type of multiple domination.

LA - eng

KW - efficient domination; multiple domination

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

ER -

## References

top- [1] D.W. Bange, A.E. Barkauskas and P.J. Slater, Disjoint dominating sets in trees, Sandia Laboratories Report, SAND 78-1087J (1978).
- [2] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient dominating sets in graphs, in: R.D. Ringeisen and F.S. Roberts (eds.) Applications of Discrete Mathematics, pages 189-199, (SIAM, Philadelphia, PA, 1988). Zbl0664.05027
- [3] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient near-domination of grid graphs, Congr. Numer. 58 (1986) 83-92.
- [4] D.W. Bange, A.E. Barkauskas, L.H. Host and P.J. Slater, Generalized domination and efficient domination in graphs, Discrete Math. 159 (1996) 1-11, doi: 10.1016/0012-365X(95)00094-D. Zbl0860.05044
- [5] N. Biggs, Perfect codes in graphs, J. Combin. Theory (B) 15 (1973) 288-296, doi: 10.1016/0095-8956(73)90042-7. Zbl0256.94009
- [6] M. Chellali, A. Khelladi and F. Maffray, Exact double domination in graphs, Discuss. Math. Graph Theory 25 (2005) 291-302, doi: 10.7151/dmgt.1282. Zbl1106.05071
- [7] G.S. Domke, S.T. Hedetniemi, R.C. Laskar and G. Fricke, Relationships between integer and fractional parameters of graphs, in: Y. Alavi, G. Chartrand, O.R. Oellermann and A.J. Schwenk (eds.), Graph Theory, Combinatorics, and Applications, Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, vol. 1, pages 371-387, (Kalamazoo, MI 1988), Wiley Publications, 1991. Zbl0840.05041
- [8] M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math. 7 (1984) 115-130, doi: 10.1016/0166-218X(84)90061-1. Zbl0531.05045
- [9] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science (Wiley, New York, 1984) 283-300.
- [10] W. Goddard and M.A. Henning, Real and integer domination in graphs, Discrete Math. 199 (1999) 61-75, doi: 10.1016/S0012-365X(98)00286-6. Zbl0928.05048
- [11] D.L. Grinstead and P.J. Slater, On the minimum intersection of minimum dominating sets in series-parallel graphs, in: Y. Alavi, G. Chartrand, O.R. Oellermann and A.J. Schwenk (eds.), Graph Theory, Combinatorics, and Applications, Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, vol. 1, pages 563-584, (Kalamazoo, MI 1988), Wiley Publications, 1991. Zbl0841.05049
- [12] D.L. Grinstead and P.J. Slater, Fractional domination and fractional packing in graphs, Congr. Numer. 71 (1990) 153-172. Zbl0691.05043
- [13] F. Harary and T.W. Haynes, Nordhaus-Gaddum inequalities for domination in graphs, Discrete Mathematics 155 (1996) 99-105, doi: 10.1016/0012-365X(94)00373-Q. Zbl0856.05053
- [14] R.R. Rubalcaba and M. Walsh, Minimum fractional dominating and maximum fractional packing functions, submitted. Zbl1215.05092
- [15] R.R. Rubalcaba and P.J. Slater, A note on obtaining k dominating sets from a k-dominating function on a tree, submitted. Zbl1139.05046
- [16] P.J. Slater, Generalized graph parameters: Gallai theorems I, Bull. Inst. of Comb. Appl. 17 (1996) 27-37. Zbl0851.05063

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.