The identification numbers of lollipop graphs

Gaixiang Cai; Fengru Xiao; Guidong Yu; Gaixiang Cai; Fengru Xiao; Guidong Yu

doi:10.3934/math.2025358

AIMS Mathematics

2025, Volume 10, Issue 4: 7813-7827. doi: 10.3934/math.2025358

Previous Article Next Article

Research article Special Issues

The identification numbers of lollipop graphs

1.
School of Mathematics and Physics, Anqing Normal University, Anqing 246133, China
2.
Department of public education, Hefei Preschool Education College, Hefei 230013, China

Received: 21 December 2024 Revised: 01 March 2025 Accepted: 24 March 2025 Published: 02 April 2025
MSC : 05C35, 05C45, 05C50

A nontrivial connected graph $ G $ with diameter $ d $ can be assigned a red-white coloring, where the vertices of $ G $ are colored either red or white, with the stipulation that at least one vertex must be red. Associated with each vertex $ v $ of $ G $ is a $ d $-vector, called the code of $ v $, whose $ i $th coordinate is the number of red vertices at distance $ i $ from $ v $. A red-white coloring of $ G $ for which distinct vertices have distinct codes is called an identification coloring or $ ID $-coloring of $ G $. A graph $ G $ possessing an $ ID $-coloring is called an $ ID $-graph. The minimum number of red vertices among all $ ID $-colorings of an $ ID $-graph $ G $ is the identification number or $ ID $-number of $ G $. The number of red vertices in an identification coloring is called the identification coloring number. This article studied the identification coloring number of lollipop graphs by constructing vertex colorings.
- lollipop graph,
- identification number,
- $ d $-vector,
- diameter,
- $ ID $-coloring
Citation: Gaixiang Cai, Fengru Xiao, Guidong Yu. The identification numbers of lollipop graphs[J]. AIMS Mathematics, 2025, 10(4): 7813-7827. doi: 10.3934/math.2025358

Related Papers:

Abstract

A nontrivial connected graph $ G $ with diameter $ d $ can be assigned a red-white coloring, where the vertices of $ G $ are colored either red or white, with the stipulation that at least one vertex must be red. Associated with each vertex $ v $ of $ G $ is a $ d $-vector, called the code of $ v $, whose $ i $th coordinate is the number of red vertices at distance $ i $ from $ v $. A red-white coloring of $ G $ for which distinct vertices have distinct codes is called an identification coloring or $ ID $-coloring of $ G $. A graph $ G $ possessing an $ ID $-coloring is called an $ ID $-graph. The minimum number of red vertices among all $ ID $-colorings of an $ ID $-graph $ G $ is the identification number or $ ID $-number of $ G $. The number of red vertices in an identification coloring is called the identification coloring number. This article studied the identification coloring number of lollipop graphs by constructing vertex colorings.

References

[1]	P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975), 549–559.
[2]	F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191–195.
[3]	G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105 (2000), 99–113. https://doi.org/10.1016/s0166-218x(00)00198-0 doi: 10.1016/s0166-218x(00)00198-0
[4]	G. Chartrand, P. Zhang, The theory and applications of resolvability in graphs, Congr. Numer., 160 (2003), 47–68.
[5]	P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci., 22 (1988), 445–455.
[6]	M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Statist., 3 (1993), 203–236. https://doi.org/10.1080/10543409308835060 doi: 10.1080/10543409308835060
[7]	M. A. Johnson, Browsable structure-activity datasets, Advances in molecular similarity, 2 (1998), 153–170.
[8]	F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, P. Valicov, Identification, location-domination and metric dimension on interval and permutation graphs. Ⅰ. Bounds, Theoret. Comput. Sci., 668 (2017), 43–58. https://doi.org/10.1016/j.tcs.2017.01.006 doi: 10.1016/j.tcs.2017.01.006
[9]	F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, P. Valicov, Identification, location-domination and metric dimension on interval and permutation graphs. Ⅱ. Algorithms and complexity, Algorithmica, 78 (2017), 914–944. https://doi.org/10.1007/s00453-016-0184-1 doi: 10.1007/s00453-016-0184-1
[10]	M. Hauptmann, R. Schmied, C. Viehmann, Approximation complexity of metric dimension problem, J. Discrete Algorithms, 14 (2012), 214–222. https://doi.org/10.1016/j.jda.2011.12.010 doi: 10.1016/j.jda.2011.12.010
[11]	C. Hernando, M. Mora, I. M. Pelayo, C. Seara, D. R. Wood, Extremal graph theory for metric dimension and diameter, Electron. J. Combin., 17 (2010), 1–28. https://doi.org/10.37236/302 doi: 10.37236/302
[12]	P. Zhang, Color-induced graph colorings, Cham: Springer, 2015. https://doi.org/10.1007/978-3-319-20394-2
[13]	P. Zhang, A kaleidoscopic view of graph colorings, Cham: Springer, 2016. https://doi.org/10.1007/978-3-319-30518-9
[14]	G. Chartrand, Y. Kono, P. Zhang, Distance vertex identification in graphs, J. Interconnect. Netw., 21 (2021), 2150005. https://doi.org/10.1142/s0219265921500055 doi: 10.1142/s0219265921500055
[15]	Y. Kono, P. Zhang, Vertex identification in trees, Discrete Math. Lett., 7 (2021), 66–73. https://doi.org/10.47443/dml.2021.0042. doi: 10.47443/dml.2021.0042
[16]	Y. Kono, 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 doi: 10.47443/dml.2021.0073
[17]	Y. Kono, P. Zhang, Vertex identification in grids and prisms, J. Interconnect. Netw., 22 (2022), 2150019. https://doi.org/10.1142/s0219265921500195 doi: 10.1142/s0219265921500195

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)