Metric dimension of dual polar graphs. (English) Zbl 1512.05406
Summary: A resolving set for a graph \(\Gamma\) is a collection of vertices \(S\), chosen so that for each vertex \(v\), the list of distances from \(v\) to the members of \(S\) uniquely specifies \(v\). The metric dimension \(\mu (\Gamma)\) is the smallest size of a resolving set for \(\Gamma\). We consider the metric dimension of the dual polar graphs, and show that it is at most the rank over \(\mathbb{R}\) of the incidence matrix of the corresponding polar space. We then compute this rank to give an explicit upper bound on the metric dimension of dual polar graphs, as well as the halved dual polar graphs.
MSC:
| 05E30 | Association schemes, strongly regular graphs |
| 05C12 | Distance in graphs |
| 51E20 | Combinatorial structures in finite projective spaces |
References:
| [1] | Babai, L., On the order of uniprimitive permutation groups, Ann. of Math. (2), 113, 553-568 (1981) · Zbl 0485.20002 · doi:10.2307/2006997 |
| [2] | Bailey, RF, The metric dimension of small distance-regular and strongly regular graphs, Aust. J. Combin., 62, 18-34 (2015) · Zbl 1321.05287 |
| [3] | Bailey, RF, On the metric dimension of imprimitive distance-regular graphs, Ann. Combin., 20, 641-659 (2016) · Zbl 1360.05185 · doi:10.1007/s00026-016-0334-9 |
| [4] | Bailey, RF, On the metric dimension of incidence graphs, Discrete Math., 341, 1613-1619 (2018) · Zbl 1384.05076 · doi:10.1016/j.disc.2018.03.001 |
| [5] | Bailey, RF; Cameron, PJ, Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc., 43, 209-242 (2011) · Zbl 1220.05030 · doi:10.1112/blms/bdq096 |
| [6] | Bailey, RF; Meagher, K., On the metric dimension of Grassmann graphs, Discrete Math. Theor. Comput. Sci., 13, 4, 97-104 (2011) · Zbl 1286.05035 |
| [7] | Bailey, RF; Cáceres, J.; Garijo, D.; González, A.; Márquez, A.; Meagher, K.; Puertas, ML, Resolving sets for Johnson and Kneser graphs, European J. Combin., 34, 736-751 (2013) · Zbl 1259.05051 · doi:10.1016/j.ejc.2012.10.008 |
| [8] | Bartoli, D.; Héger, T.; Kiss, Gy; Takáts, M., On the metric dimension of affine planes, biaffine planes and generalized quadrangles, Aust. J. Combin., 72, 226-248 (2018) · Zbl 1410.51007 |
| [9] | Bartoli, D., Kiss, Gy., Marcugini, S., Pambianco, F.: Resolving sets for higher dimensional projective spaces. Finite Fields Appl. 67, 101723, 14 pp. (2020) · Zbl 1464.51008 |
| [10] | Bartoli, D.; Kiss, Gy; Marcugini, S.; Pambianco, F., On resolving sets in the point-line incidence graph of \({\rm PG}(n,q)\), Ars Math. Contemp., 19, 231-247 (2020) · Zbl 1465.05024 · doi:10.26493/1855-3974.2125.7b0 |
| [11] | Blumenthal, LM, Theory and Applications of Distance Geometry (1953), Oxford: Clarendon Press, Oxford · Zbl 0050.38502 |
| [12] | Brouwer, AE; Cohen, AM; Neumaier, A., Distance-Regular Graphs (1989), Berlin: Springer, Berlin · Zbl 0747.05073 · doi:10.1007/978-3-642-74341-2 |
| [13] | Brouwer, AE; van Maldeghem, H., Strongly Regular Graphs (2022), Cambridge: Cambridge University Press, Cambridge · Zbl 1498.05001 · doi:10.1017/9781009057226 |
| [14] | De Bruyn, B., An Introduction to Incidence Geometry (2016), Cham: Birkhäuser/Springer, Cham · Zbl 1376.51001 · doi:10.1007/978-3-319-43811-5 |
| [15] | Feng, M.; Wang, K., On the metric dimension of bilinear forms graphs, Discrete Math., 312, 1266-1268 (2012) · Zbl 1239.05052 · doi:10.1016/j.disc.2011.11.020 |
| [16] | Gravier, S., Parreau, A., Rottey, S., Storme, L., Vandomme, É.: Identifying codes in vertex-transitive graphs and strongly regular graphs. Electron. J. Combin. 22(4), Paper 4.6, 26 pp. (2015) · Zbl 1323.05141 |
| [17] | Guo, H., Gao, Y.: Class dimension of association schemes in singular linear spaces. Discrete Math. Algorithms Appl. 9(1), 1750005, 5 pp. (2017) · Zbl 1369.05219 |
| [18] | Guo, J.; Wang, K.; Li, F., Metric dimension of symplectic dual polar graphs and symmetric bilinear forms graphs, Discrete Math., 313, 186-188 (2013) · Zbl 1256.05057 · doi:10.1016/j.disc.2012.09.023 |
| [19] | Guo, J.; Wang, K.; Li, F., Metric dimension of some distance-regular graphs, J. Comb. Optim., 26, 190-197 (2013) · Zbl 1298.90121 · doi:10.1007/s10878-012-9459-x |
| [20] | Guo, J.; Li, F.; Wang, K., Incidence matrices of finite attenuated spaces and class dimension of association schemes, Discrete Math., 315-316, 42-46 (2014) · Zbl 1278.05249 · doi:10.1016/j.disc.2013.10.003 |
| [21] | Guo, J.; Wang, K.; Li, F., Resolving sets for four families of distance-regular graphs, Adv. Geom., 14, 129-134 (2014) · Zbl 1282.05039 · doi:10.1515/advgeom-2013-0021 |
| [22] | Guo, J.; Li, F.; Wang, K., On class dimension of flat association schemes in affine and affine-symplectic spaces, Finite Fields Appl., 39, 43-51 (2016) · Zbl 1333.05322 · doi:10.1016/j.ffa.2016.01.004 |
| [23] | Harary, F.; Melter, RA, On the metric dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118 |
| [24] | Héger, T., Takáts, M.: Resolving sets and semi-resolving sets in finite projective planes. Electron. J. Combin. 19(14), Paper 30, 21 pp. (2012) · Zbl 1266.05020 |
| [25] | Héger, T., Kiss, Gy., Nakić, A. Storme, L.: Identifying codes for generalized quadrangles. Submitted for publication · Zbl 07809268 |
| [26] | Héger, T.; Szilárd, P.; Takáts, M., The metric dimension of the incidence graphs of projective and affine planes of small order, Aust. J. Combin., 78, 352-375 (2020) · Zbl 1453.05027 |
| [27] | Payne, SE; Thas, JA, Finite Generalized Quadrangles (2009), Zürich: European Mathematical Society, Zürich · Zbl 1247.05047 · doi:10.4171/066 |
| [28] | Slater, PJ, Leaves of trees, Congr. Numer., 14, 549-568 (1975) · Zbl 0316.05102 |
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.
