The Alternative of Sensor Placement in Multi-Story Buildings through the Metric Dimension Approach: A Representation of Generalized Petersen Graphs

Authors

  • Asmiati Universitas Lampung
  • Akmal Junaidi Universitas Lampung
  • Ahmad Ari Aldino Universitas Teknokrat Indonesia
  • Arif Munandar Universitas Lampung

DOI:

https://doi.org/10.21512/comtech.v13i2.7268

Keywords:

metric dimension, sensor placement, multistory building, Petersen graph, Python programming

Abstract

In a public facility or private office where many people can get together, a fire detection device is a mandatory tool as an emergency alarm in the facility. However, the expense of the installation of the device is a troublesome matter. So, optimization is needed to minimize the number of these devices. The way to implement is to select the appropriate position to place the devices in public facilities. The research discussed the placement of the sensors in multi-story buildings. The multi-story buildings could be represented as cube composition graphs with the number of rooms, and the connectivity between the floor and its rooms was equal. The concept of this multi-story building was modeled into a generalized Petersen graph where a vertex represented a room, and an edge was the connectivity of rooms. The basis obtained on that metric dimension was represented as a sensor placed on the building. Then, the optimization of device placement was seen as determining the metric dimensions of the Petersen graph. In the research, the alternative sensor placements were computed using the graph metric dimension approach implemented in Python. The research successfully implements the metric dimension of  to  using Python code to obtain the alternative of its basis. A basic alternative indicates the location of the device placement like fire detectors, network access points, or other sensors inside a building.

Dimensions

Plum Analytics

Author Biographies

Asmiati, Universitas Lampung

Mathematics Department, Faculty of Mathematics and Natural Sciences

Akmal Junaidi, Universitas Lampung

Department of Computer Science, Faculty of Mathematics and Natural Sciences

Ahmad Ari Aldino, Universitas Teknokrat Indonesia

Informatics Department, Faculty of Engineering and Computer Science

Arif Munandar, Universitas Lampung

Department of Computer Science, Faculty of Mathematics and Natural Sciences

References

Adawiyah, R., Agustin, I. H., Prihandini, R. M., Alfarisi, R., & Albirri, E. R. (2019). On the local multiset dimension of m-shadow graph. Journal of Physics: Conference Series, 1211, 1–9. https://doi.org/10.1088/1742-6596/1211/1/012006

Adawiyah, R., Prihandini, R. M., Albirri, E. R., Agustin, I. H., & Alfarisi, R. (2019). The local multiset dimension of unicyclic graph. In IOP Conference Series: Earth and Environmental Science (pp. 1–8). IOP Publishing. https://doi.org/10.1088/1755-1315/243/1/012075

Alfarisi, R., Dafik, D., Kristiana, A. I., & Agustin, I. H. (2019). The local multiset dimension of graphs. IJET, 8(3), 120–124.

Asmiati, A., Aldino, A. A., Notiragayu, N., Zakaria, L., & Anshori, M. (2020). Dimensi metrik hasil operasi tertentu pada graf Petersen diperumum. Limits: Journal of Mathematics and Its Applications, 16(2), 87–93. https://doi.org/10.12962/limits.v16i2.5594

Bača, M., Baskoro, E. T., Salman, A. N. M., Saputro, S. W., & Suprijanto, D. (2011). The metric dimension of regular bipartite graphs. Bulletin Mathématique de La Société Des Sciences Mathématiques de Roumanie, 54(102), 15–28. https://www.jstor.org/stable/43679200

Chartrand, G., Eroh, L., Johnson, M. A., & Oellermann, O. R. (2000). Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105(1–3), 99–113. https://doi.org/10.1016/S0166-218X(00)00198-0

Dudenko, M., & Oliynyk, B. (2017). On unicyclic graphs of metric dimension 2. Algebra and Discrete Mathematics, 23(2), 216–222.

Hernando, C., Mora, M., Pelayo, I. M., Seara, C., & Wood, D. R. (2010). Extremal graph theory for metric dimension and diameter. The Electronic Journal of Combinatorics, 17(1), 1–28. https://doi.org/10.37236/302

Imran, M., Siddiqui, M. K., & Naeem, R. (2018). On the metric dimension of generalized Petersen multigraphs. IEEE Access, 6, 74328–74338. https://doi.org/10.1109/ACCESS.2018.2883556

Okamoto, F., Phinezy, B., & Zhang, P. (2010). The local metric dimension of a graph. Mathematica Bohemica, 135(3), 239–255. https://doi.org/10.21136/MB.2010.140702

Saenpholphat, V., & Zhang, P. (2004). Conditional resolvability in graphs: A survey. International Journal of Mathematics and Mathematical Sciences, 2004, 1997–2017. https://doi.org/10.1155/S0161171204311403

Saputro, S. W., Mardiana, N., & Purwasih, I. A. (2017). The metric dimension of comb product graphs. Matematicki Vesnik, 69(4), 248–258.

Saputro, S. W., Simanjuntak, R., Uttunggadewa, S., Assiyatun, H., Baskoro, E. T., Salman, A. N. M., & Bača, M. (2013). The metric dimension of the lexicographic product of graphs. Discrete Mathematics, 313(9), 1045–1051. https://doi.org/10.1016/j.disc.2013.01.021

Simanjuntak, R., Uttunggadewa, S., & Saputro, S. W. (2013). Metric dimension of amalgamation of graphs. Retrieved from https://arxiv.org/abs/1312.0191

Susilowati, L., Sa’adah, I., Fauziyyah, R. Z., Erfanian, A., & Slamin. (2020). The dominant metric dimension of graphs. Heliyon, 6(3), 1–6. https://doi.org/10.1016/j.heliyon.2020.e03633

Downloads

Published

2022-11-25

Issue

Section

Articles
Abstract 188  .
PDF downloaded 866  .