Geodesic
The Compared Costs of Domination Location-Domination and Identification
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 127-147.

Voir la notice de l'article provenant de la source Library of Science

Let G = (V, E) be a finite graph and r ≥ 1 be an integer. For v ∈ V, let Br(v) = x ∈ V : d(v, x) ≤ r be the ball of radius r centered at v. A set C ⊆ V is an r-dominating code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅; it is an r-locating-dominating code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅, and for any two distinct non-codewords x ∈ V C, y ∈ V C, we have Br(x) ∩ C ≠ Br(y) ∩ C; it is an r-identifying code if for all v ∈ V, we have Br(v) ∩ C ≠ ∅, and for any two distinct vertices x ∈ V, y ∈ V, we have Br(x) ∩ C ≠ Br(y) ∩ C. We denote by γr(G) (respectively, ldr(G) and idr(G)) the smallest possible cardinality of an r-dominating code (respectively, an r-locating-dominating code and an r-identifying code). We study how small and how large the three differences idr(G)−ldr(G), idr(G)−γr(G) and ldr(G) − γr(G) can be.
Keywords: graph theory, dominating set, locating-dominating code, identifying code, twin-free graph 
@article{DMGT_2020_40_1_a8,
     author = {Hudry, Olivier and Lobstein, Antoine},
     title = {The {Compared} {Costs} of {Domination} {Location-Domination} and {Identification}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {127--147},
     publisher = {mathdoc},
     volume = {40},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a8/}
}
TY  - JOUR
AU  - Hudry, Olivier
AU  - Lobstein, Antoine
TI  - The Compared Costs of Domination Location-Domination and Identification
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 127
EP  - 147
VL  - 40
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a8/
LA  - en
ID  - DMGT_2020_40_1_a8
ER  - 
%0 Journal Article
%A Hudry, Olivier
%A Lobstein, Antoine
%T The Compared Costs of Domination Location-Domination and Identification
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 127-147
%V 40
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a8/
%G en
%F DMGT_2020_40_1_a8
Hudry, Olivier; Lobstein, Antoine. The Compared Costs of Domination Location-Domination and Identification. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 1, pp. 127-147. http://geodesic.mathdoc.fr/item/DMGT_2020_40_1_a8/

[1] C. Berge, Graphes (Gauthier-Villars, Paris, 1983).

[2] C. Berge, Graphs (North-Holland Publishing Co., Amsterdam, 1985).

[3] N. Bertrand, Codes identifiants et codes localisateurs-dominateurs sur certains graphes, Mémoire de stage de maîtrise, ENST (Paris, France, 2001).

[4] I. Charon, O. Hudry and A. Lobstein, Possible cardinalities for identifying codes in graphs, Australas. J. Combin. 32 (2005) 177–195.

[5] I. Charon, O. Hudry and A. Lobstein, Possible cardinalities for locating-dominating codes in graphs, Australas. J. Combin. 34 (2006) 23–32.

[6] I. Charon, O. Hudry and A. Lobstein, Extremal cardinalities for identifying and locating-dominating codes in graphs, Discrete Math. 307 (2007) 356–366. doi:10.1016/j.disc.2005.09.027

[7] C.J. Colbourn, P.J. Slater and L.K. Stewart, Locating dominating sets in series parallel networks, Congr. Numer. 56 (1987) 135–162.

[8] R. Diestel, Graph Theory (Springer-Verlag, Berlin, 2005).

[9] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287–293. doi:10.1007/BF01848079

[10] F. Foucaud, E. Guerrini, M. Kovše, R. Naserasr, A. Parreau and P. Valicov, Extremal graphs for the identifying code problem, European J. Combin. 32 (2011) 628–638. doi:10.1016/j.ejc.2011.01.002

[11] S. Gravier, R. Klasing and J. Moncel, Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs, Algorithmic Oper. Res. 3 (2008) 43–50.

[12] S. Gravier and J. Moncel, On graphs having a V \ { x } set as an identifying code, Discrete Math. 307 (2007) 432–434. doi:10.1016/j.disc.2005.09.035

[13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[14] M.G. Karpovsky, K. Chakrabarty and L.B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 44 (1998) 599–611. doi:10.1109/18.661507

[15] A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs, a bibliography . https://www.lri.fr/~lobstein/debutBIBidetlocdom.pdf

[16] O. Ore, Theory of Graphs (American Mathematical Society, Providence, 1962). doi:10.1090/coll/038

[17] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23–32. doi:10.1002/jgt.3190060104

[18] P.J. Slater, Domination and location in graphs, Research Report 93 (National University of Singapore, 1983).