On the Identification Numbers of Lobster Graphs

Articles in Press

Document Type : Original paper

Authors

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

Abstract

Given a nontrivial connected undirected graph $G$ with diameter $d$, a vertex coloring $c$ of $G$ that uses only the colors red and white induces, for each $v \in V(G)$, the $d$-vector $\vec{d}(v) = [a_1 a_2 \cdots a_d]$, where each $a_i$ is equal to the number of red vertices of distance $i$ from $v$. Then $c$ is called an ID-coloring of $G$ if $\vec{d}(v) \neq \vec{d}(w)$ for all distinct $v,w \in V(G)$. If $G$ has at least one ID-coloring, then it is called an ID-graph and its identification number $ID(G)$ is defined to be the minimum number of red vertices among all ID-colorings of $G$. The notions of ID-colorings and identification number have been shown to be equivalent to the notions of multiset resolving sets and multiset dimension, respectively. Previous works on this topic have focused on characterizing ID-caterpillars and ID-lobsters and on the identification numbers of some ID-caterpillars. In this paper, we focus on the identification numbers of ID-lobsters. Specifically, we establish a sharp lower bound for the identification number of all ID-lobsters. Furthermore, we characterize and determine the identification numbers of all uniform ID-lobsters.

Keywords

Main Subjects

References

[1] R.T. Chan Sim, A.J.E.E. Diga, and A. J.R. Loyola, Identification coloring of lobster graphs, Undergraduate thesis, Ateneo de Manila University, 2024.
[2] G. Chartrand, Y. Kono, and P. Zhang, Distance vertex identification in graphs, J. Interconnect. Netw. 21 (2021), no. 01, Article ID: 2150005.  https://doi.org/10.1142/S0219265921500055
[3] Y. Hafidh, R. Kurniawan, S. Saputro, R. Simanjuntak, S. Tanujaya, and S. Uttunggadewa, Multiset dimensions of trees, 2019, https://doi.org/10.48550/arXiv.1908.05879
[4] A. Hakanen and I.G. Yero, Complexity and equivalency of multiset dimension and ID-colorings, 2023,  https://doi.org/10.48550/arXiv.2303.06986
[5] 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
[6] V. Khemmani and S. Isariyapalakul, The characterization of caterpillars with multidimension 3, Thai J. Math. Annual Meeting in Mathematics 2019 (2020), 247–259.
[7] Y. Kono and P. Zhang, Vertex identification in trees, Discrete Math. Lett. 7 (2021), 66–73. https://doi.org/10.47443/dml.2021.0042
[8] 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
[9] Y. Kono and P. Zhang, Vertex identification in grids and prisms, J. Interconnect. Netw. 22 (2022), no. 02, Article ID: 2150019. https://doi.org/10.1142/S0219265921500195
[10] 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
[11] V. Saenpholphat, On multiset dimension in graphs, Academic SWU 1 (2009), 193–202.
[12] R. Simanjuntak, P. Siagian, and T. Vetrik, The multiset dimension of graphs, 2019, https://doi.org/10.48550/arXiv.1711.00225
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 18 July 2025

Files

Share

How to cite

Statistics