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

Abstract

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

How to cite

top

Robert 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. [1] D.W. Bange, A.E. Barkauskas and P.J. Slater, Disjoint dominating sets in trees, Sandia Laboratories Report, SAND 78-1087J (1978). 
  2. [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. [3] D.W. Bange, A.E. Barkauskas and P.J. Slater, Efficient near-domination of grid graphs, Congr. Numer. 58 (1986) 83-92. 
  4. [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. [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. [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. [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. [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. [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. [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. [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. [12] D.L. Grinstead and P.J. Slater, Fractional domination and fractional packing in graphs, Congr. Numer. 71 (1990) 153-172. Zbl0691.05043
  13. [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. [14] R.R. Rubalcaba and M. Walsh, Minimum fractional dominating and maximum fractional packing functions, submitted. Zbl1215.05092
  15. [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. [16] P.J. Slater, Generalized graph parameters: Gallai theorems I, Bull. Inst. of Comb. Appl. 17 (1996) 27-37. Zbl0851.05063

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.