The fractional $k$-truncated metric dimension of graphs

Abstract

The metric dimension, $\dim (G)$, and the fractional metric dimension, ${\dim }_f(G)$, of a graph $G$ have been studied extensively. Let $G$ be a graph with vertex set $V(G)$, and let $d(x,y)$ denote the length of a shortest $x-y$ path in $G$. Let $k$ be a positive integer. For any $x,y\in V(G)$, let $d_k(x,y)=\min \{d(x,y),k+1\}$ and let $R_k\{x,y\}=\{z\in V(G):d_k(x,z)\ne d_k(y,z)\}$. A set $S\subseteq V(G)$ is a \emph{$k$-truncated resolving set} of $G$ if $|S\cap R_k\{x,y\}|\ge 1$ for any distinct $x,y\in V(G)$, and the \emph{$k$-truncated metric dimension} ${\dim }_k(G)$ of $G$ is the minimum cardinality over all $k$-truncated resolving sets of $G$. For a function $g$ defined on $V(G)$ and for $U\subseteq V(G)$, let $g(U)={\sum }_{s\in U}g(s)$. A real-valued function $g:V(G)\to [0,1]$ is a \emph{$k$-truncated resolving function} of $G$ if $g(R_k\{x,y\})\ge 1$ for any distinct $x,y\in V(G)$, and the \emph{fractional $k$-truncated metric dimension} ${\dim }_{k,f}(G)$ of $G$ is $\min\{g(V(G)): g \mbox{ is a $k$-truncated resolving function of }G\}$. Note that ${\dim }_{k,f}(G)$ reduces to ${\dim }_k(G)$ if the codomain of $k$-truncated resolving functions is restricted to $\{0,1\}$, and ${\dim }_{k,f}(G)={\dim }_f(G)$ if $k$ is at least the diameter of $G$. In this paper, we study the fractional $k$-truncated metric dimension of graphs. For any connected graph $G$ of order $n\ge 2$, we show that $1\le {\dim }_{k,f}(G)\le \frac{n}{2}$; we characterize $G$ satisfying ${\dim }_{k,f}(G)$ equals $1$ and $\frac{n}{2}$, respectively. We examine ${\dim }_{k,f}(G)$ of some graph classes. We also show the existence of non-isomorphic graphs $G$ and $H$ such that ${\dim }_k(G)={\dim }_k(H)$ and ${\dim }_{k,f}(G)\ne {\dim }_{k,f}(H)$, and we examine the relation among $\dim (G)$, ${\dim }_f(G)$, ${\dim }_k(G)$ and ${\dim }_{k,f}(G)$. We conclude the paper with some open problems.

14 pages, 2 figures

References in corpus (2)

• Broadcast Dimension of Graphs
• The distance-k dimension of graphs