Further contributions on the outer multiset dimension of graphs

Abstract

The outer multiset dimension ${\dim }_{\mathrm{ms}}(G)$ of a graph $G$ is the cardinality of a smallest set of vertices that uniquely recognize all the vertices outside this set by using multisets of distances to the set. It is proved that ${\dim }_{\mathrm{ms}}(G)=n(G)-1$ if and only if $G$ is a regular graph with diameter at most $2$. Graphs $G$ with ${\dim }_{\mathrm{ms}}(G)=2$ are described and recognized in polynomial time. A lower bound on the lexicographic product of $G$ and $H$ is proved when $H$ is complete or edgeless, and the extremal graphs are determined. It is proved that ${\dim }_{\mathrm{ms}}(P_s\square P_t)=3$ for $s\ge t\ge 2$.

16 pages