Bounds on perfect k-domination in trees: an algorithmic approach

• Autorzy: Chaluvaraju B. , Vidya K. A.
• Języki publikacji: EN

Abstrakty

EN

Let k be a positive integer and G = (V, E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G if every vertex v of G not in D is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k -dominating set of G is the perfect k-domination number γkp (G ). In this paper, a sharp bound for γkp (T) is obtained where T is a tree.

Słowa kluczowe

EN

k-domination; perfect domination; perfect k-domination

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2012
• Tom: Vol. 32, no. 4
• Strony: 707--714
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Chaluvaraju B.

autor

Vidya K. A.

• Department of Mathematics Bangalore University Central College Campus Bangalore -560 001, India,

Bibliografia

• [1] B.D. Acharya, H.B. Walikar, E. Sampathkumar, Recent developments in the theory of domination in graphs, Mehta Research Institute, Allahabad, MRI Lecture Notes in Math., 1979.
• [2] D. W. Bange, A.E. Barkauskas, P.J. Slater, Efficient dominating sets in graphs, [in:] R.D. Ringeisen, F.S. Roberts, eds, Applications of Discrete Mathematics (SIAM, Philadelphia, 1988), 189–199.
• [3] E.J. Cockayne, B.L. Hartnell, S.T. Hedetniemi, R. Laskar, Perfect domination in graphs, J. Combin. Inform. System Sci. 18 (1993), 136–148.
• [4] B. Chaluvaraju, M. Chellali, K.A. Vidya, k-Perfect domination in graphs, Australasian Journal of Combinatorics 48 (2010), 175–184.
• [5] I.J. Dejter, J. Pujol, Perfect Domination and Symmetry, Congr. Numer. 111 (1995) 18–32.
• [6] M.R. Fellows, M.N. Hoover, Perfect domination. Australasian Journal of Combinatorics 3 (1991), 141–150.
• [7] J.F. Fink, M.S. Jacobson, n-domination in graphs, [in:] Y. Alavi and A. J. Schwenk,eds, Graph Theory with Applications to Algorithms and Computer Science, Wiley, NewYork, 1985, 283–300.
• [8] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, San Francisco, 1979.
• [9] F. Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969.
• [10] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker, Inc., New York, 1998.
• [11] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in graphs: Advanced topics, Marcel Dekker, Inc., New York, 1998.
• [12] M. Livingston, Q.F. Stout, Perfect dominating sets, Congr. Numer. 79 (1990), 187–203.