On weak metric dimension of digraphs. (English) Zbl 1516.05052
Summary: Using the two-way distance, we introduce the concept of the weak metric dimension of a strongly connected digraph \(\Gamma\). We first establish lower and upper bounds for the number of arcs in \(\Gamma\) by using the diameter and weak metric dimension of \(\Gamma\), and characterize all digraphs attaining the lower or upper bound. Then we study a digraph with weak metric dimension 1 and classify all vertex-transitive digraphs having weak metric dimension 1. Finally, all digraphs of order \(n\) with weak metric dimension \(n-1\) or \(n-2\) are determined.
MSC:
| 05C12 | Distance in graphs |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Abas, M. and Vetrík, T., Metric dimension of Cayley digraphs of split metacyclic groups, Theor. Comput. Sci.809 (2020) 61-72. · Zbl 1439.05067 |
| [2] | Bailey, R. F. and Cameron, P. J., Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc.43 (2011) 209-242. · Zbl 1220.05030 |
| [3] | Boutin, D., Goliber, V. H. and Pelto, M., Identifying codes on directed de Bruijn graphs, Discrete Appl. Math.262 (2019) 29-41. · Zbl 1411.05099 |
| [4] | Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihal’ák, M. and Ram, L. S., Network discovery and verification, IEEE J. Selected Areas Commun.24 (2006) 2168-2181. |
| [5] | Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L., Seara, C. and Wood, D. R., On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math.21 (2007) 423-441. · Zbl 1139.05314 |
| [6] | Chartrand, G., Eroh, L., Johnson, M. A. and Oellermann, O. R., Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math.105 (2000) 99-113. · Zbl 0958.05042 |
| [7] | Chartrand, G., Rains, M. and Zhang, P., The directed distance dimension of oriented graphs, Math. Bohemica125 (2000) 155-168. · Zbl 0963.05045 |
| [8] | Chartrand, G., Rains, M. and Zhang, P., On the dimension of oriented graphs, Utilitas Math.60 (2001) 139-151. · Zbl 1011.05020 |
| [9] | Chvátal, V., Mastermind, Combinatorica3 (1983) 325-329. · Zbl 0717.05002 |
| [10] | Fehr, M., Gosselin, S. and Oellermann, O. R., The metric dimension of Cayley digraphs, Discrete Math.306 (2006) 31-41. · Zbl 1085.05034 |
| [11] | Feng, M., Xu, M. and Wang, K., On the metric dimension of line graphs, Discrete Appl. Math.161 (2013) 802-805. · Zbl 1262.05069 |
| [12] | Harary, F. and Melter, R. A., On the metric dimension of a graph, Ars Combinatoria2 (1976) 191-195. · Zbl 0349.05118 |
| [13] | Khuller, S., Raghavachari, B. and Rosenfeld, A., Landmarks in graphs, Discrete Appl. Math.70 (1996) 217-229. · Zbl 0865.68090 |
| [14] | Sebő, A. and Tannier, E., On metric generators of graphs, Math. Oper. Res.29 (2004) 383-393. · Zbl 1082.05032 |
| [15] | Slater, P. J., Leaves of trees, Congr. Numerantium14 (1975) 549-559. · Zbl 0316.05102 |
| [16] | Suzuki, H., Thin weakly distance-regular digraphs, J. Combin. Theory Ser. B92 (2004) 69-83. · Zbl 1052.05069 |
| [17] | Vetrík, T., On the metric dimension of directed and undirected circulant graphs, Discuss. Math. Graph Theory40 (2020) 67-76. · Zbl 1437.05114 |
| [18] | Wang, K. and Suzuki, H., Weakly distance-regular digraphs, Discrete Math.264 (2003) 225-236. · Zbl 1014.05077 |
| [19] | Wang, K., Commutative weakly distance-regular digraphs of girth 2, Eur. J. Combin.25 (2004) 363-375. · Zbl 1034.05050 |
| [20] | Yang, Y., Lv, B. and Wang, K., Weakly distance-regular digraphs of valency three, I, Electron. J. Combin.23(2) (2016) 2.12. · Zbl 1335.05077 |
| [21] | Yang, Y., Lv, B. and Wang, K., Weakly distance-regular digraphs of valency three, II, J. Combin. Theory Ser. A160 (2018) 288-315. · Zbl 1394.05055 |
| [22] | Yang, Y., Lv, B. and Wang, K., Quasi-thin weakly distance-regular digraphs, J. Algebraic Combin.51 (2020) 19-50. · Zbl 1434.05070 |
| [23] | Yang, Y. and Wang, K., Thick weakly distance-regular digraphs, Graphs Combin.38 (2022) 37. · Zbl 1484.05209 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
