The non-isolated resolving number of a graph Cartesian product with a complete graph

Abstract

A set of vertices $W$ resolves a graph $G$ if every vertex of $G$ is uniquely determined by its vector of distances to the vertices in $W$. A resolving set $W$ of $G$ is called a non-isolated resolving set if the induced subgraph of $G$ by $W$ does not contain an isolated vertex. An $\nr$-set of $G$ is a non isolated resolving set with minimum cardinality and the non-isolated resolving number of $G$ refers to its cardinality, denoted by $\nr(G)$. Let $K_n$ be a complete graph of order $n$. In this paper, for any graph $G$ of order $m$ with $m\le n$, we determine the sharp lower and upper bounds of the non-isolated resolving number of $G$ Cartesian product with a complete graph, denoted by $\nr(G\times K_n)$. We provide the non-isolated resolving number of $G\times K_n$ for some classes of $G$, namely paths, complete graphs, cycles, friendship graphs, and star graphs. We also show that for any positive integers $c\le \lfloor\frac{m}{2}\rfloor$, there exists a graph $G$ of order $m$ such that $\nr(G\times K_n)$ is equal to the upper bound minus $c$.