Let $ G = (V, E) $ be a simple connected graph. A vertex $ x\in V(G) $ resolves the elements $ u, v\in E(G)\cup V(G) $ if $ d_G(x, u)\neq d_G(x, v) $. A subset $ S\subseteq V(G) $ is a mixed metric resolving set for $ G $ if every two elements of $ G $ are resolved by some vertex of $ S $. A set of smallest cardinality of mixed metric generator for $ G $ is called the mixed metric dimension. In this paper trees and unicyclic graphs having mixed dimension three are classified. The main aim is to investigate the structure of a simple connected graph having mixed dimension three with respect to the order of graph, maximum degree of basis elements and distance partite sets of basis elements. In particular to find necessary and sufficient conditions for a graph to have mixed metric dimension 3. Moreover three separate algorithms are developed for trees, unicyclic graphs and in general for simple connected graph $ J_{n}\ncong P_{n} $ with $ n\geq 3 $ to determine "whether these graphs have mixed dimension three or not?". If these graphs have mixed dimension three, then these algorithms provide a mixed basis of an input graph.
Citation: Dalal Awadh Alrowaili, Uzma Ahmad, Saira Hameeed, Muhammad Javaid. Graphs with mixed metric dimension three and related algorithms[J]. AIMS Mathematics, 2023, 8(7): 16708-16723. doi: 10.3934/math.2023854
Let $ G = (V, E) $ be a simple connected graph. A vertex $ x\in V(G) $ resolves the elements $ u, v\in E(G)\cup V(G) $ if $ d_G(x, u)\neq d_G(x, v) $. A subset $ S\subseteq V(G) $ is a mixed metric resolving set for $ G $ if every two elements of $ G $ are resolved by some vertex of $ S $. A set of smallest cardinality of mixed metric generator for $ G $ is called the mixed metric dimension. In this paper trees and unicyclic graphs having mixed dimension three are classified. The main aim is to investigate the structure of a simple connected graph having mixed dimension three with respect to the order of graph, maximum degree of basis elements and distance partite sets of basis elements. In particular to find necessary and sufficient conditions for a graph to have mixed metric dimension 3. Moreover three separate algorithms are developed for trees, unicyclic graphs and in general for simple connected graph $ J_{n}\ncong P_{n} $ with $ n\geq 3 $ to determine "whether these graphs have mixed dimension three or not?". If these graphs have mixed dimension three, then these algorithms provide a mixed basis of an input graph.
| [1] |
U. Ahmad, S. Ahmed, Muhammad Javaid, M. N. Alam, Computing Fault-tolerant Metric Dimension of Connected Graphs, J. Math., 2022 (2022), Article ID 9773089. https://doi.org/10.1155/2022/97730892022 doi: 10.1155/2022/97730892022
|
| [2] |
R. C. Brigham, G. Chartrand, R. D. Dutton, P. Zhang, Resolving domination in graphs, Math. Bohem., 128 (2003), 325–364. https://doi.org/10.21136/MB.2003.134179 doi: 10.21136/MB.2003.134179
|
| [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. |
| [4] |
G. Chartrand, V. Saenpholphat, P. Zhang, The independent resolving number of a graph, Math. Bohem., 128 (2003), 379–393. https://doi.org/10.21136/MB.2003.134003 doi: 10.21136/MB.2003.134003
|
| [5] | A. Estrada-Moreno, J. A. Rodriguez-Velazquez, I. G. Yero, The k-metric dimension of a graph, Appl. Math. Inf. Sci., 9 (2015), 2829–2840. |
| [6] |
M. M. Danasa, J. Kraticab, A. Savic, Z. Maksimovic, Some new general lower bounds for mixed metric dimension of graphs, Filomat, 35 (2021). https://doi.org/10.2298/FIL2113275M doi: 10.2298/FIL2113275M
|
| [7] | F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combinatoria, 2 (1976), 191–195. |
| [8] |
A. Kelenc, N. Tratnik, I. G. Yero, Uniquely identifying the edges of a graph: the edge metric dimension, Discrete Appl. Math., 251 (2018), 204–220. https://doi.org/10.1016/j.dam.2018.05.052 doi: 10.1016/j.dam.2018.05.052
|
| [9] |
A. Kelenc, D. Kuzia, A. Taranenko, I. G. Yero, Mixed metric dimension of graphs, Appl. Math. Comput., 314 (2017), 429–438. https://doi.org/10.1016/j.amc.2017.07.027 doi: 10.1016/j.amc.2017.07.027
|
| [10] | S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), 217–229. |
| [11] |
O. R. Oellermann, J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discret Appl. Math., 155 (2007), 356–364. https://doi.org/10.1016/j.dam.2006.06.009 doi: 10.1016/j.dam.2006.06.009
|
| [12] |
F. Okamoto, B. Phinezyn, P. Zhang, The local metric dimension of a graph, Math. Bohem., 135 (2010), 239–255. https://doi.org/10.21136/MB.2010.140702 doi: 10.21136/MB.2010.140702
|
| [13] | H. Razza, Y. Ji, Computing the Mixed Metric Dimension of a Generalized Petersen Graph $P(n, 2)$, Front. Phys., 28 July 2020. https://doi.org/10.3389/fphy.2020.00211 |
| [14] | P. J. Slater, Leaves of trees, Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium, 14 (1975), 549–559. |
| [15] |
J. Sedlar, R. Škrekovsk, Mixed metric dimension of graphs with edge disjoint cycles, Discrete Appl. Math., 300 (2021), 1–8. https://doi.org/10.1016/j.dam.2021.05.004 doi: 10.1016/j.dam.2021.05.004
|
| [16] | G. Sudhakara, A. R. Hemanth Kumar, Graphs with metric dimension two a characterization, Adv. Appl. Discrete Math., 4 (2009), 169–186. |
Figures(3)
Dalal Awadh Alrowaili, Uzma Ahmad, Saira Hameeed, Muhammad Javaid. Graphs with mixed metric dimension three and related algorithms[J]. AIMS Mathematics, 2023, 8(7): 16708-16723. doi: 10.3934/math.2023854
DownLoad: