Multiset Dimension of Prisms

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, Ateneo de Manila University, Quezon City, Philippines

Abstract

Given a subset $W$ of the vertex set of a graph $G$, the representation multiset $r_m(v|W)$ of a vertex $v$ is the multiset of distances between $v$ and each vertex in $W$. The subset $W$ is called an m-resolving set of $G$ if distinct vertices have distinct representation multisets. Introduced independently by Saenpholphat and Simanjuntak et al., the m-resolving sets of a graph can be used to uniquely identify its vertices. The notion of m-resolving sets has been shown to be equivalent to identification colorings that have been introduced by Chartrand et al. More recently, Kono and Zhang have established that the prism $K_2 \Box C_n$ has an m-resolving set (equivalently, identification coloring) if and only if $n \geq 6$. In this work, we extend their result by determining the multiset dimension of prisms; that is, we determine the minimum cardinality of their m-resolving sets.

Keywords

Main Subjects

References

[1] R. Alfarisi, Y. Lin, J. Ryan, Dafik, and I.H. Agustin, A note on multiset dimension and local multiset dimension of graphs, Stat. Optim. Inf. Comput. 8 (2020), no. 4, 890–901.  https://doi.org/10.19139/soic-2310-5070-727
[2] G. Chartrand, L. Eroh, M. Johnson, and O. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), no. 1-3, 91–113.  https://doi.org/10.1016/S0166-218X(00)00198-0
[3] G. Chartrand, Y. Kono, and P. Zhang, Distance vertex identification in graphs, J. Interconnect. Netw. 21 (2021), no. 1, Article ID: 2150005.  https://doi.org/10.1142/S0219265921500055
[4] Y. Hafidh, R. Kurniawan, S. Saputro, R. Simanjuntak, S. Tanujaya, and S. Uttunggadewa, Multiset dimensions of trees, 2019.
[5] Anni Hakanen and Ismael G. Yero, Complexity and equivalency of multiset dimension and id-colorings, Fundamenta Informaticae 191 (2024), no. 3–4, 315–330.
[6] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
[7] S. Isariyapalakul, V. Khemmani, and W. Pho-on, The multibases of symmetric caterpillars, J. Math. 2020 (2020), no. 1, Article ID: 5210628. https://doi.org/10.1155/2020/5210628
[8] V. Khemmani and S. Isariyapalakul, The multiresolving sets of graphs with prescribed multisimilar equivalence classes, Int. J. Math. Math. Sci. 2018 (2018), no. 1, Article ID: 8978193. https://doi.org/10.1155/2018/8978193
[9] V. Khemmani and S. Isariyapalakul, The characterization of caterpillars with multidimension 3, Thai J. Math. (2020), 247–259.
[10] Y. Kono and P. Zhang, Vertex identification in trees, Discrete Math. Lett. 7 (2021), 66–73. https://doi.org/10.47443/dml.2021.0042
[11] Y. Kono and P. Zhang, A note on the identification numbers of caterpillars, Discrete Math. Lett. 8 (2022), 10–15.
https://doi.org/10.47443/dml.2021.0073
[12] Y. Kono and P. Zhang, Vertex identification in grids and prisms, J. Interconnect. Netw. 22 (2022), no. 2, Article ID: 2150019.  https://doi.org/10.1142/S0219265921500195
[13] J.B. Liu, S.K. Sharma, V.K. Bhat, and H. Raza, Multiset and mixed metric dimension for starphene and zigzag-edge coronoid, Polycycl. Aromat. Compd. 43  (2023), no. 1, 190–204. https://doi.org/10.1080/10406638.2021.2019066
[14] R.M. Marcelo, M.A.C. Tolentino, A.D. Garciano, M.J.P. Ruiz, and J.C. Buot, On the vertex identification spectra of grids, J. Interconnect. Netw. 25 (2025), no. 1, Article ID: 2450002.  https://doi.org/10.1142/S0219265924500026.
[15] V. Saenpholphat, On multiset dimension in graphs, Academic SWU 1 (2009), 193-202.
[16] Rinovia Simanjuntak, Presli Siagian, and Tomas Vetrik, The multiset dimension of graphs, 2019.
[17] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 March 2025

Files

Share

How to cite

Statistics