The compared costs of domination location-domination and identification (Q2282469)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The compared costs of domination location-domination and identification |
scientific article |
Statements
The compared costs of domination location-domination and identification (English)
0 references
8 January 2020
0 references
Let \(G\) be a graph and \(\{u\in V(G):d_G(u,v)\leq r\}\) is a ball of radius \(r\in\mathbb{N}\) centered at \(v\in V(G)\) and denoted by \(B_r(v)\). We say that \(x,y\in V(G)\) are \(r\)-twins if \(B_r(x)=B_r(y)\). A set \(D_1\subseteq V(G)\) is an \(r\)-dominating code of \(G\) if \(D_1\cap B_r(v)\neq\emptyset\) for every \(v\in V(G)\). The minimum cardinality of an \(r\)-dominating code of \(G\) is denoted by \(\gamma_r(G)\). A set \(D_2\subseteq V(G)\) is an \(r\)-locating-dominating code of \(G\) if \(D_2\cap B_r(v)\neq\emptyset\) for every \(v\in V(G)\) and for any two distinct \(x,y\in V(G)-D_2\) we have \(D_2\cap B_r(x)\neq D_2\cap B_r(y)\). The minimum cardinality of an \(r\)-locating-dominating code of \(G\) is denoted by \(ld_r(G)\). A set \(D_3\subseteq V(G)\) is an \(r\)-identifying code of \(G\) if \(D_3\cap B_r(v)\neq\emptyset\) for every \(v\in V(G)\) and for any two distinct \(x,y\in V(G)\) we have \(D_3\cap B_r(x)\neq D_3\cap B_r(y)\). The minimum cardinality of an \(r\)-identifying code of \(G\) is denoted by \(id_r(G)\). From the definitions, it follows that \[ \gamma_r(G)\leq ld_r(G)\leq id_r(G). \] In the present paper, the minimum and maximum difference between the mentioned parameters is studied on connected graphs that contain no \(r\)-twins or contain some \(r\)-twins.
0 references
\(r\)-dominating code
0 references
\(r\)-locating-dominating code
0 references
\(r\)-identifying code
0 references