Article in volume
Authors:
Title:
Optimal error-detecting open-locating-dominating set on the infinite triangular grid
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 445-455
Received: 2020-06-07 , Revised: 2020-10-22 , Accepted: 2020-10-24 , Available online: 2020-11-18 , https://doi.org/10.7151/dmgt.2374
Abstract:
Let $G$ be a graph and $S \subseteq V(G)$ represent a subset of vertices having
installed ``detectors," each of which is capable of sensing an ``intruder" in
its open-neighborhood. The open-locating-code of $v \in V(G)$ is the set of
neighboring detectors, $N(v) \cap S$. The set $S$ is said to be an
open-locating-dominating set if every open-locating-code is unique and non-empty.
In this paper we focus on error-detecting open-locating-dominating sets on the
infinite triangular grid, present a solution with density $\frac{1}{2}$, and
prove it is optimal.
Keywords:
domination, open-locating-dominating set, error-detection, triangular grid, density
References:
- R. Dantas, F. Havet and R.M. Sampaio, Identifying codes for infinite triangular grids with a finite number of rows, Discrete Math. 340 (2017) 1584–1597.
https://doi.org/10.1016/j.disc.2017.02.015 - I. Honkala, An optimal locating-dominating set in the infinite triangular grid, Discrete Math. 306 (2006) 2670–2681.
https://doi.org/10.1016/j.disc.2006.04.028 - R. Kincaid, A. Oldham and G. Yu, On optimal open locating-dominating sets in infinite triangular grids, Discrete Appl. Math. 193 (2015) 139–144.
https://doi.org/10.1016/j.dam.2015.04.024 - S.J. Seo, Open-locating-domination sets in the infinite king grid, J. Combin. Math. Combin. Comput. 104 (2018) 31–47.
- S.J. Seo and P.J. Slater, Open neighborhood locating-dominating sets, Australas. J. Combin. 46 (2010) 109–119.
- S.J. Seo and P.J. Slater, Graphical parameters for classes of tumbling block graphs, Congr. Numer. 213 (2012) 155–168.
- S.J. Seo and P.J. Slater, Fault tolerant detectors for distinguishing sets in graphs, Discuss. Math. Graph Theory 35 (2015) 797–818.
https://doi.org/10.7151/dmgt.1838 - P.J. Slater, Fault-tolerant locating-dominating sets, Discrete Math. 249 (2002) 179–189.
https://doi.org/10.1016/S0012-365X(01)00244-8 - P.J. Slater, A framework for faults in detectors within network monitoring systems, WSEAS Trans. Math. 12 (2013) 911–916.
- Watching systems, identifying, locating-dominating and discriminating codes in graphs.
https://www.lri.fr/\%7elobstein/debutBIBidetlocdom.pdf
Close