On the Metric Dimension and Spectrum of Graphs

Articles in Press

Document Type : Original paper

Authors

1 Master Program of Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

2 Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Bandung, Indonesia

3 Center for Research Collaboration on Graph Theory and Combinatorics, Indonesia

Abstract

The algebraic approach to graph theoretical problems has been extensively studied by looking at the spectrum of a graph's representation matrix. In this paper, we investigate some relationships between the metric dimension of a graph $G$ and its nullity, that is, the multiplicity of eigenvalue $0$ in the adjacency matrix of $G$, and the eigenvalues of its Laplacian and distance matrices. Furthermore, we also present a relationship between the metric dimension of a graph and its nullity, using twin classes.

Keywords

Main Subjects

References

[1] S. Akhter and R. Farooq, Metric dimension of fullerene graphs, Electron. J. Graph Theory Appl. 7 (2019), no. 1, 91–103.
https://doi.org/10.5614/ejgta.2019.7.1.7
[2] S. Arumugam and R.A. Kumar, Distance similar sets in graphs, Util. Math. 102 (2017), 265–281.
[3] R.B. Bapat, Graphs and Matrices, Springer, London, 2010.
[4] E.T. Baskoro, Dimensi dalam Graf, ITB Press, Bandung, 2023. 
[5] N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1993.
[6] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), no. 1–3, 99–113.
https://doi.org/10.1016/S0166-218X(00)00198-0
[7] R. Chen, S. Fazal, A. Aslam, F. Tchier, and M.A. Binyamin, On the metric dimension of graphs associated with irreducible and Arf numerical semigroups, AKCE Int. J. Graphs Comb. (2024), In press.
https://doi.org/10.1080/09728600.2024.2350582
[8] D. Cvetković, P. Rowlinson, and S. Simić, An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010.
[9] D.M. Cvetković and I. Gutman, The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat. Vesn. 9 (1972), no. 56, 141–150.
[10] R. Diestel, Graph Theory, Springer, Berlin, 2017
[11] I. Faria, Permanental roots and the star degree of a graph, Linear Algebra Appl. 64 (1985), 255–265.
https://doi.org/10.1016/0024-3795(85)90281-2
[12] T.H. Foregger, Identities related to permanents of doubly stochastic matrices and series reduces trees, Linear Multilinear Algebra 7 (1979), no. 1, 37–41.
https://doi.org/10.1080/03081087908817257
[13] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979.
[14] R. Grone, R. Merris, and V.S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990), no. 2, 218–238
https://doi.org/10.1016/j.camwa.2004.05.005
[15] I. Gutman and B. Borovicanin, Nullity of graphs: an updated survey, Zbornik Radova 14 (2011), no. 22, 137–154.
[16] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
[17] J. Haslegrave, Extremal results on average subtree density of series-reduced trees, J. Combin. Theory Ser. B 107 (2014), 26–41.
https://doi.org/10.1016/j.jctb.2014.02.003
[18] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, and D.R. Wood, Extremal graph theory for metric dimension and diameter., Electron. J. Comb. 17 (2010), no. 1, Article number: R30
https://doi.org/10.37236/302
[19] H. Iswadi, E.T. Baskoro, R. Simanjuntak, and A.N.M. Salman, The metric dimension of graph with pendant edges, J. Comb. Math. Comb. Comput. 65 (2008), 139–145.
[20] S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996), no. 3, 217–229.
https://doi.org/10.1016/0166-218X(95)00106-2
[21] D. Kuziak and I.G. Yero, Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results, arXiv:2107.04877 (2021).
[22] G. Matsaglia and G. PH Styan, Equalities and inequalities for ranks of matrices, Linear Multilinear Algebra 2 (1974), no. 3, 269–292.
https://doi.org/10.1080/03081087408817070
[23] R. Merris, The distance spectrum of a tree, J. Graph Theory 14 (1990), no. 3, 365–369.
https://doi.org/10.1002/jgt.3190140309
[24] V. Saenpholphat and P. Zhang, Some results on connected resolvability in graphs, Congr. Numer. 158 (2002), 5–20.
[25] S.K. Sharma, V.K. Bhat, and P. Singh, On metric dimension of some planar graphs with 2n odd sided faces, Discrete Math. Algorithms Appl. 16 (2024), no. 1, Article ID: 2250185.
https://doi.org/10.1142/S1793830922501853
[26] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
[27] R.C. Tillquist, R.M. Frongillo, and M.E. Lladser, Getting the lay of the land in discrete space: A survey of metric dimension and its applications, SIAM Rev. 65 (2023), no. 4, 919–962.
https://doi.org/10.1137/21M1409512
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 31 August 2024

Files

Share

How to cite

Statistics