Interplay between the local metric dimension and the clique number of a graph

Abstract

The local metric dimension ${\dim }_l$ in relation to the clique number $\omega$ is investigated. It is proved that if $\omega (G)\le n(G)-3$, then ${\dim }_l(G)\le n(G)-3$ and the graphs attaining the bound classified. Moreover, the graphs $G$ with ${\dim }_l(G)=n(G)-3$ are listed (with no condition on the clique number). It is proved that if $\omega (G)=n(G)-2$, then $n(G)-4\le {\dim }_l(G)\le n(G)-3$, and all graphs are divided into two groups depending on which of the options applies. The conjecture asserting that for any graph $G$ we have ${\dim }_l(G)\le \left[(\omega (G)-2)/(\omega (G)-1)\right]\cdot n(G)$ is proved for all graphs with $\omega (G)\in \{n(G)-1,n(G)-2,n(G)-3\}$. A negative answer is given for the problem whether every planar graph fulfills the inequality ${\dim }_l(G)\le \lceil (n(G)+1)/2\rceil$.