Minimal locating-paired-dominating sets in triangular and king grids
Keywords:
Locating-dominating set, Triangular grid, King gridAbstract
Let G = (V,E) be a finite or infinite graph. A set S ? V is paired-dominating if
S induces a matching in G and S dominates all vertices of G. A set S ? V is locating
if for any two distinct vertices u, v in V \ S, N(u) ? S 6= N(v) ? S, where N(u) and
N(v) are open neighborhoods of vertices u and v. We find the minimal density of
locating-paired-dominating sets in the infinite triangular grid, which is equal to 4/15.
We also present bounds for the minimal density D of locating-paired-dominating sets
in the infinite king grid, which is 3/14 ? D ? 2/9
References
Haynes, T.W., & Slater, P.J. (1995). Paired-domination
and the paired-domatic number. Congressus Numerantium,
, 65- 72.
Haynes, T.W., & Slater, P.J. (1998). Paired-domination in
graphs. Networks, 32(3), 199- 206.
Haynes, T.W., Hedetniemi, S.T., & Slater, P.J. (1998).
Fundamentals of Domination in Graphs. Marcel Dekker,
New York: Taylor & Francis.
Honkala, I. (2006). An optimal locating-dominating set in
the infinite triangular grid. Discrete Mathematics, 306 (21),
- 2681.
Honkala, I., & Laihonen, T. (2006). On locating-dominating
sets in infinite grids. European Journal of Combinatorics,
(2), 218- 227.
McCoy, J., & Henning, M.A. (2009). Locating and paireddominating
sets in graphs. Discrete Applied Mathematics,
(15), 3268 -3280.
Niepel, L. (2015). Locating–-paired--dominating sets in
square grids. Discrete Mathematics, 338(10), 1699 -1705.
Slater, P.J. (2002). Fault-tolerant locating-dominating sets.
Discrete Mathematics, 249(1 -3), 179- 189.
