2021/08/05 by Yi, Eunjeong
#05C12 #05C38 #05C72 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.02745
The metric dimension, dim(G), and the fractional metric dimension, dimf(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 ∈ V(G), let dk(x,y)=min\d(x,y), k+1\ and let Rk\x,y\=\z∈ V(G): dk(x,z) ≠ dk(y,z)\. A set S ⊆ V(G) is a k-truncated resolving set of G if |S ∩ Rk\x,y\| ≥ 1 for any distinct x,y∈ V(G), and the k-truncated metric dimension dimk(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 ⊆ V(G), let g(U)=∑s∈ Ug(s). A real-valued function g:V(G) →[0,1] is a k-truncated resolving function of G if g(Rk\x,y\) ≥ 1 for any distinct x, y∈ V(G), and the fractional k-truncated metric dimension dimk,f(G) of G is min\g(V(G)): g is a k-truncated resolving function of G\. Note that dimk,f(G) reduces to dimk(G) if the codomain of k-truncated resolving functions is restricted to \0,1\, and dimk,f(G)=dimf(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≥2, we show that 1 ≤ dimk,f(G) ≤ (n)/(2); we characterize G satisfying dimk,f(G) equals 1 and (n)/(2), respectively. We examine dimk,f(G) of some graph classes. We also show the existence of non-isomorphic graphs G and H such that dimk(G)=dimk(H) and dimk,f(G)≠ dimk,f(H), and we examine the relation among dim(G), dimf(G), dimk(G) and dimk,f(G). We conclude the paper with some open problems.