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


  • Mariam Kinawi
  • Zaid Hussain Computer Sciece Kuwait University
  • Ludovit Niepel


Locating-dominating set, Triangular grid, King grid


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

Author Biography

Zaid Hussain, Computer Sciece Kuwait University

Dr. Zaid A. Hussain (also known as Zaid Dashti) received the B.Sc. degree in Computer Science from Kuwait University, Kuwait, in 2006, the M.Sc. and Ph.D. degrees in Computer Science from Oregon State University, USA, in 2008 and 2011, respectively. Since 2011, he has been with Kuwait University, Kuwait, where he is an assistant professor with the Computer Science Department.


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.