The fractional $k$-metric dimension of graphs

Abstract

Let $G$ be a graph with vertex set $V(G)$. For any two distinct vertices $x$ and $y$ of $G$, let $R\{x,y\}$ denote the set of vertices $z$ such that the distance from $x$ to $z$ is not equal to the distance from $y$ to $z$ in $G$. For a function $g$ defined on $V(G)$ and for $U\subseteq V(G)$, let $g(U)={\sum }_{s\in U}g(s)$. Let $κ(G)=\min\{|R\{x,y\}|: x\neq y \mbox{ and } x,y \in V(G)\}$. For any real number $k\in [1,\kappa (G)]$, a real-valued function $g:V(G)\to [0,1]$ is a \emph{$k$-resolving function} of $G$ if $g(R\{x,y\})\ge k$ for any two distinct vertices $x,y\in V(G)$. The \emph{fractional $k$-metric dimension}, ${\dim }_f^k(G)$, of $G$ is $\min\{g(V(G)): g \mbox{ is a $k$-resolving function of } G\}$. In this paper, we initiate the study of the fractional $k$-metric dimension of graphs. For a connected graph $G$ and $k\in [1,\kappa (G)]$, it's easy to see that $k\le {\dim }_f^k(G)\le \frac{k|V(G)|}{\kappa (G)}$; we characterize graphs $G$ satisfying ${\dim }_f^k(G)=k$ and ${\dim }_f^k(G)=|V(G)|$, respectively. We show that ${\dim }_f^k(G)\ge k{\dim }_f(G)$ for any $k\in [1,\kappa (G)]$, and we give an example showing that ${\dim }_f^k(G)-k{\dim }_f(G)$ can be arbitrarily large for some $k\in (1,\kappa (G)]$; we also describe a condition for which ${\dim }_f^k(G)=k{\dim }_f(G)$ holds. We determine the fractional $k$-metric dimension for some classes of graphs, and conclude with two open problems, including whether $\varphi (k)={\dim }_f^k(G)$ is a continuous function of $k$ on every connected graph $G$.

15 pages, 1 figure

References in corpus (2)

• The k-metric dimension of a graph
• The fractional strong metric dimension in three graph products