Let $ V(G) $ be the vertex set of a simple and connected graph $ G $. A subset $ S\subseteq V(G) $ is a distance-equalizer set of $ G $ if, for every pair of vertices $ u, v\in V(G)\setminus S $, there exists a vertex in $ S $ that is equidistant to $ u $ and $ v $. The minimum cardinality among the distance-equalizer sets of $ G $ is the equidistant dimension of $ G $, denoted by $ \xi(G) $. In this paper, we studied the problem of finding $ \xi(G\circ H) $, where $ G\circ H $ denotes the lexicographic product of two graphs $ G $ and $ H $. The aim was to express $ \xi(G\circ H) $ in terms of parameters of $ G $ and $ H $. In particular, we considered the cases in which $ G $ has a domination number equal to one, as well as the cases where $ G $ is a path or a cycle, among others. Furthermore, we showed that $ \xi(G)\le \xi(G\circ H)\le \xi(G)|V(H)| $ for every connected graph $ G $ and every graph $ H $ and we discussed the extreme cases. We also showed that the general problem of finding the equidistant dimension of a graph is NP-hard.
Citation: Adrià Gispert-Fernández, Juan Alberto Rodríguez-Velázquez. The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs[J]. AIMS Mathematics, 2024, 9(6): 15325-15345. doi: 10.3934/math.2024744
Let $ V(G) $ be the vertex set of a simple and connected graph $ G $. A subset $ S\subseteq V(G) $ is a distance-equalizer set of $ G $ if, for every pair of vertices $ u, v\in V(G)\setminus S $, there exists a vertex in $ S $ that is equidistant to $ u $ and $ v $. The minimum cardinality among the distance-equalizer sets of $ G $ is the equidistant dimension of $ G $, denoted by $ \xi(G) $. In this paper, we studied the problem of finding $ \xi(G\circ H) $, where $ G\circ H $ denotes the lexicographic product of two graphs $ G $ and $ H $. The aim was to express $ \xi(G\circ H) $ in terms of parameters of $ G $ and $ H $. In particular, we considered the cases in which $ G $ has a domination number equal to one, as well as the cases where $ G $ is a path or a cycle, among others. Furthermore, we showed that $ \xi(G)\le \xi(G\circ H)\le \xi(G)|V(H)| $ for every connected graph $ G $ and every graph $ H $ and we discussed the extreme cases. We also showed that the general problem of finding the equidistant dimension of a graph is NP-hard.
| [1] |
B. S. Anand, M. Changat, S. Klavžar, I. Peterin, Convex sets in lexicographic products of graphs, Graphs Combin., 28 (2012), 77–84. https://doi.org/10.1007/s00373-011-1031-4 doi: 10.1007/s00373-011-1031-4
|
| [2] |
G. A. Barragán-Ramírez, A. Estrada-Moreno, Y. Ramírez-Cruz, J. A. Rodríguez-Velázquez, The local metric dimension of the lexicographic product of graphs, Bull. Malays. Math. Sci. Soc., 42 (2019), 2481–2496. https://doi.org/10.1007/s40840-018-0611-3 doi: 10.1007/s40840-018-0611-3
|
| [3] | K. Casel, A. Estrada-Moreno, H. Fernau, J. A. Rodríguez-Velázquez, Weak total resolvability in graphs, Discuss. Math. Graph Theory, 36 (2016), 185–210. |
| [4] |
A. Estrada-Moreno, C. García-Gómez, Y. Ramírez-Cruz, J. A. Rodríguez-Velázquez, The simultaneous strong metric dimension of graph families, Bull. Malays. Math. Sci. Soc., 39 (2016), 175–192. https://doi.org/10.1007/s40840-015-0268-0 doi: 10.1007/s40840-015-0268-0
|
| [5] |
A. Estrada-Moreno, I. G. Yero, J. A. Rodríguez-Velázquez, Relationships between the 2-metric dimension and the 2-adjacency dimension in the lexicographic product of graphs, Graphs Combin., 32 (2016), 2367–2392. https://doi.org/10.1007/s00373-016-1736-5 doi: 10.1007/s00373-016-1736-5
|
| [6] |
A. Estrada-Moreno, I. G. Yero, J. A. Rodríguez-Velázquez, The $k$-metric dimension of the lexicographic product of graphs, Discrete Math., 339 (2016), 1924–1934. https://doi.org/10.1016/j.disc.2015.12.024 doi: 10.1016/j.disc.2015.12.024
|
| [7] | M. Feng, K. S. Wang, On the fractional metric dimension of corona product graphs and lexicographic product graphs, 2012, arXiv: 1206.1906. |
| [8] | M. R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, New York: W. H. Freeman and Company, 1979. |
| [9] |
A. González, C. Hernando, M. Mora, The equidistant dimension of graphs, Bull. Malays. Math. Sci. Soc., 45 (2022), 1757–1775. https://doi.org/10.1007/s40840-022-01295-z doi: 10.1007/s40840-022-01295-z
|
| [10] | R. Hammack, W. Imrich, S. Klavžar, Handbook of product graphs, 2 Eds., Boca Raton: CRC Press, 2011. https://doi.org/10.1201/b10959 |
| [11] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of domination in graphs, Boca Raton: CRC Press, 1998. https://doi.org/10.1201/9781482246582 |
| [12] | T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in graphs: Volume 2: Advanced topics, New York: Routledge, 1998. https://doi.org/10.1201/9781315141428 |
| [13] | M. A. Henning, A. Yeo, Total domination in graphs, New York: Springer, 2013. https://doi.org/10.1007/978-1-4614-6525-6 |
| [14] | W. Imrich, S. Klavžar, Product graphs: structure and recognition, New York: Wiley, 2000. |
| [15] |
M. Jannesari, B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Math., 312 (2012), 3349–3356. https://doi.org/10.1016/j.disc.2012.07.025 doi: 10.1016/j.disc.2012.07.025
|
| [16] |
C. X. Kang, I. G. Yero, E. Yi, The fractional strong metric dimension in three graph products, Discrete Appl. Math., 251 (2018), 190–203. https://doi.org/10.1016/j.dam.2018.05.051 doi: 10.1016/j.dam.2018.05.051
|
| [17] |
S. Klavžar, D. Kuziak, I. Peterin, I. G. Yero, A Steiner general position problem in graph theory, Comput. Appl. Math., 40 (2021), 223. https://doi.org/10.1007/s40314-021-01619-y doi: 10.1007/s40314-021-01619-y
|
| [18] |
S. Klavžar, D. Kuziak, I. G. Yero, Further contributions on the outer multiset dimension of graphs, Results Math., 78 (2023), 50. https://doi.org/10.1007/s00025-022-01829-8 doi: 10.1007/s00025-022-01829-8
|
| [19] |
S. Klavžar, P. K. Neethu, S. V. Ullas Chandran, The general position achievement game played on graphs, Discrete Appl. Math., 317 (2022), 109–116. https://doi.org/10.1016/j.dam.2022.04.019 doi: 10.1016/j.dam.2022.04.019
|
| [20] |
S. Klavžar, I. G. Yero, The general position problem and strong resolving graphs, Open Math., 17 (2019), 1126–1135. https://doi.org/10.1515/math-2019-0088 doi: 10.1515/math-2019-0088
|
| [21] |
D. Kuziak, I. G. Yero, J. A. Rodríguez-Velázquez, Closed formulae for the strong metric dimension of lexicographic product graphs, Discuss. Math. Graph Theory, 36 (2016), 1051–1064. https://doi.org/10.7151/dmgt.1911 doi: 10.7151/dmgt.1911
|
| [22] |
I. Peterin, I. G. Yero, Edge metric dimension of some graph operations, Bull. Malays. Math. Sci. Soc., 43 (2020), 2465–2477. https://doi.org/10.1007/s40840-019-00816-7 doi: 10.1007/s40840-019-00816-7
|
| [23] |
Y. Ramírez-Cruz, A. Estrada-Moreno, J. A. Rodríguez-Velázquez, The simultaneous metric dimension of families composed by lexicographic product graphs, Graphs Combin., 32 (2016), 2093–2120. https://doi.org/10.1007/s00373-016-1675-1 doi: 10.1007/s00373-016-1675-1
|
| [24] | J. A. Rodríguez-Velázquez, Lexicographic metric spaces: basic properties and the metric dimension, Appl. Anal. Discrete Math., 14 (2020), 20–32. |
| [25] |
J. A. Rodríguez-Velázquez, Solution of the Chen-Chvátal conjecture for specific classes of metric spaces, AIMS Math., 6 (2021), 7766–7781. https://doi.org/10.3934/math.2021452 doi: 10.3934/math.2021452
|
| [26] |
S. W. Saputro, R. Simanjuntak, S. Uttunggadewa, H. Assiyatun, E. T. Baskoro, A. N. M. Salman, et al., The metric dimension of the lexicographic product of graphs, Discrete Math., 313 (2013), 1045–1051. https://doi.org/10.1016/j.disc.2013.01.021 doi: 10.1016/j.disc.2013.01.021
|
Figures(6)
Adrià Gispert-Fernández, Juan Alberto Rodríguez-Velázquez. The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs[J]. AIMS Mathematics, 2024, 9(6): 15325-15345. doi: 10.3934/math.2024744
DownLoad: