Vertices belonging to all or to no minimum locating dominating sets of trees

• Autorzy: Blidia M. , Lounes R.
• Języki publikacji: EN

Abstrakty

EN

A set D of vertices in a graph G is a locating-dominating set if for every two vertices u, v of G \ D the sets N(u) ∩ D and N (v) ∩ D are non-empty and different. In this paper, we characterize vertices that are in all or in no minimum locating dominating sets in trees. The characterization guarantees that the γL-excellent tree can be recognized in a polynomial time.

Słowa kluczowe

EN

domination; locating domination

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2009
• Tom: Vol. 29, no. 1
• Strony: 5--14
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Blidia M.

autor

Lounes R.

• University of Blida LAMDA-RO, Department of Mathematics B.P. 270, Blida, Algeria,

Bibliografia

• [1] M. Blidia, M. Chellali, S. Khelifi, Veritices belonging to all or to no minimum double dominating sets in trees, AKCE .7. Graphs. Combin. 2 (2005) 1, 1-9.
• [2] G. Chartrand, L. Lesniak, Graphs & Digraphs: Third Edition, Chapman & Hall, London, 1996.
• [3] E. J. Cockayne, M.A. Henning, C.M. Mynhardt, Vertices contained in all or in no minimum total dominating set of a tree, Discrete Math. 260 (2003), 37-44.
• [4] P.L. Hammer, P. Hansen, B. Simeone, Veritices belonging to all or to no maximum stable sets of a graph, SIAM .1. Algebraic Discrete Math. 3 (1982) 2, 511-522.
• [5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York. 1998.
• [6] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
• [7] S.T. Hedetniemi, R. C. Laskar, Bibliography on domination in graphs and some basic definitions of parameters, Discrete mathematics 86 (1990), 257-477.
• [8] C.M. Mynhardt, Vertices contained in every minimum dominating set of a tree, ,1. Graph Theory 31 (1999) 3, 163-177.
• [9] P.J. Slater, Domination and location in acyclic graphs, Networks 17 (1987), 55-64.
• [10] P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci., 22 (1988), 445-455.