Geodesic
Open Locating-Dominating Sets in Circulant Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 47-62.

Voir la notice de l'article provenant de la source Library of Science

Location detection problems have been studied for a variety of applications including finding faults in multiprocessors, contaminants in public utilities, intruders in buildings and facilities, and for environmental monitoring using wireless sensor networks. In each of these applications, the system or structure can be modeled as a graph, and sensors placed strategically at a subset of vertices can locate and detect anomalies in the system. An open locating-dominating set (OLD-set) is a subset of vertices in a graph in which every vertex in the graph has a non-empty and unique set of neighbors in the subset. Sensors placed at OLD-set vertices can uniquely detect and locate disturbances in a system. These sensors can be expensive and, as a result, minimizing the size of the OLD-set is critical. Circulant graphs, a group of regular cyclic graphs, are often used to model parallel networks. We prove the optimal OLD-set size for a particular circulant graph using Hall’s Theorem. We also consider the mixed-weight OLD-set introduced in [R.M. Givens, R.K. Kincaid, W. Mao and G. Yu, Mixed-weight open locating-dominating sets, in: 2017 Annual Conference on Information Science and Systems, (IEEE, Baltimor, 2017) 1–6] which models a system with sensors of varying strengths. To model these systems, we place weights on the vertices in the graph, representing the strength of a sensor placed at the corresponding location in the system. We study particular mixed-weight OLD-sets in cycles, which behave similarly to OLD-sets in circulant graphs, and show the optimal mixed-weight OLD-set size using the discharging method.
Keywords: open locating-dominating sets, circulant graphs, Hall’s Matching Theorem, mixed-weight open locating-dominating sets 
@article{DMGT_2022_42_1_a3,
     author = {Givens, Robin M. and Yu, Gexin and Kincaid, Rex K.},
     title = {Open {Locating-Dominating} {Sets} in {Circulant} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {47--62},
     publisher = {mathdoc},
     volume = {42},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a3/}
}
TY  - JOUR
AU  - Givens, Robin M.
AU  - Yu, Gexin
AU  - Kincaid, Rex K.
TI  - Open Locating-Dominating Sets in Circulant Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 47
EP  - 62
VL  - 42
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a3/
LA  - en
ID  - DMGT_2022_42_1_a3
ER  - 
%0 Journal Article
%A Givens, Robin M.
%A Yu, Gexin
%A Kincaid, Rex K.
%T Open Locating-Dominating Sets in Circulant Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 47-62
%V 42
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a3/
%G en
%F DMGT_2022_42_1_a3
Givens, Robin M.; Yu, Gexin; Kincaid, Rex K. Open Locating-Dominating Sets in Circulant Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 1, pp. 47-62. http://geodesic.mathdoc.fr/item/DMGT_2022_42_1_a3/

[1] I.F. Akyildiz, D. Pompili and T. Melodia, Underwater acoustic sensor networks: research challenges, Ad Hoc Networks 3 (2005) 257–279. https://doi.org/10.1016/j.adhoc.2005.01.004

[2] K. Appel and W. Haken, Every planar map is four colorable, Part I: Discharging, Illinois J. Math. 21 (1977) 249–490. https://doi.org/10.1215/ijm/1256049011

[3] T.Y. Berger-Wolf, W.E. Hart and J. Saia, Discrete sensor placement problems in distribution networks, Math. Comput. Modelling 42 (2005) 1385-1396. https://doi.org/10.1016/j.mcm.2005.03.005

[4] N. Bertrand, I. Charon, O. Hudry and A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European J. Combin. 25 (2004) 969–987. https://doi.org/10.1016/j.ejc.2003.12.013

[5] D. Cranston and G. Yu, A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid, Electron. J. Combin. 16 (2009) #R113.

[6] A. Cukierman and G. Yu, New bounds on the minimum density of an identifying code for the infinite hexagonal grid, Discrete Appl. Math. 161 (2013) 2910–2924. https://doi.org/10.1016/j.dam.2013.06.002

[7] D. Di Palma, L. Bencini, G. Collodi, G. Manes, F. Chiti, R. Fantacci and A. Manes, Disctributed monitoring systems for agriculture based on wireless sensor network technology, Internat. J. Advances in Networks and Services 3 (2010) 18–28.

[8] F. Foucaud and M.A. Henning, Location-domination and matching in cubic graphs, Discrete Math. 339 (2016) 1221–1231. https://doi.org/10.1016/j.disc.2015.11.016

[9] R.M. Givens, R.K. Kincaid, W. Mao and G. Yu, Mixed-weight open locating-dominating sets, in: 2017 Annual Conference on Information Science and Systems, (IEEE, Baltimor, 2017) 1–6. https://doi.org/10.1109/CISS.2017.7926110

[10] P. Hall, On representatives of subsets, J. London Math. Soc. (2) 10 (1935) 26–30. https://doi.org/10.1112/jlms/s1-10.37.26

[11] I. Honkala, T. Laihonen and S. Ranto, On locating-dominating codoes in binary Hamming spaces, Discrete Math. Theor. Comput. Sci. 6 (2004) 265–282.

[12] S. Janson and T. Laihonen, On the size of identifying codes in binary hypercubes, J. Combin. Theory Ser. A 116 (2009) 1087–1096. https://doi.org/10.1016/j.jcta.2009.02.004

[13] R.K. Kincaid, A. Oldham and G. Yu, 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

[14] M. Laifenfeld and A. Trachtenberg, Identifying codes and covering problems, IEEE Trans. Inform. Theory 54 (2008) 3929–3950. https://doi.org/10.1109/TIT.2008.928263

[15] M. Laifenfeld, A. Trachtenberg, R. Cohen and D. Starobinski, Joint monitoring and routing in wireless sensor networks using robust identifying codes, in: 2007 4th International Conference on Broadband Communications, Networks and System, (IEEE, Releigh, 2007) 197–206. https://doi.org/10.1109/BROADNETS.2007.4550425

[16] A. Lobstein, Watching systems, identyfying, locating-dominating and discriminating codes in graphs (a bibliography), 2017.

[17] A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk and J. Anderson, Wireless sensor networks for habitat monitoring, in: Proc. First ACM International Workshop on Wireless Sensor Networks and Application, (ACM, Atlanta, 2002) 88–97. https://doi.org/10.1145/570738.570751

[18] P.D. Manual, Locating and liar domination of circulant networks, Ars Combin. 101 (2011) 309–320.

[19] P. Padhy, K. Martinez, A. Riddoch, H.L.R. Ong and J.K. Hart, Glacial environment monitoring using sensor networks, in: Proc. Real-World Wireless Sensor Networks, (ACM, Stockholm, 2005) 10–14.

[20] S. Ray, D. Starobinski, A. Trachtenberg and R. Ungrangsi, Robust location detection with sensor networks, IEEE J. Selected Areas in Communications 22 (2004) 1016–1025. https://doi.org/10.1109/JSAC.2004.830895

[21] S.J. Seo and P.J. Slater, Open neighborhood locating-dominating sets, Australas. J. Combin. 46 (2010) 109–120.

[22] S.J. Seo and P.J. Slater, Open neighborhood locating-domination for grid-like graphs, Bull. Inst. Combin. Appl. 65 (2012) 89–100.

[23] E. Vallejo, R. Beivide and C. Martinez, Practicable layouts for optimal circulant graphs, in: 13th Euromicro Conference on Parallel, Distributed and Network-Based Processing, (IEEE, Lugano, 2005) 118–125. https://doi.org/10.1109/EMPDP.2005.32