Further results on the metric dimension and spectrum of graphs

Abstract

The concept of metric dimension in graphs has the aim of finding a set of vertices in a graph with the smallest size that can be used as a reference to identify all vertices in the graph uniquely. Formally, let \(G\) be a connected graph, and let \(S = \{s_1,\dots,s_k\} \subseteq V(G)\) be an ordered set. For every \(v \in V(G)\), we define \(r(v|S) = (d(v,s_1),\dots,d(v,s_k))\) where \(d\) is the distance function of \(G\). We call \(S\) a resolving set if \(r(u|S) \neq r(v|S)\) for every \(u,v\in V(G)\), \(u \neq v\). The metric dimension of \(G\), denoted by \(\dim(G)\), is the smallest integer \(k\) such that \(G\) has a resolving set of size \(k\). Recently, the authors have initiated research on the relation between the metric dimension of a graph and its nullity (that is, the multiplicity of \(0\) in its adjacency spectrum), and we have obtained several results. In this paper, we present some new relationships between the metric dimension and the spectrum of graphs. In detail, we present an inequality involving the metric dimension and nullity of any bipartite or singular graph. Then, we give an infinite class of graphs having equal metric dimension and nullity using the rooted product of graphs. Finally, for any connected graph \(G\) other than a path, we show that a submatrix of the distance matrix of \(G\), associated with a minimal resolving set of \(G\), has the full-rank property.