# Minimal locating-paired-dominating sets in triangular and king grids

## Keywords:

Locating-dominating set, Triangular grid, King grid## Abstract

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.