The Fractional Strong Metric Dimension of Graphs
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
For any two vertices x and y of a graph G, let S {x, y } denote the set of vertices z such that either x lies on a y - z geodesic or y lies on a x - z geodesic. For a function g defined on V (G) and U V (G), let g (U ) = xU g (x). A function g : V (G) [0, 1] is a strong resolving function of G if g (S {x, y }) 1, for every pair of distinct vertices x, y of G. The fractional strong metric dimension, sdimf (G), of a graph G is min{g (V (G)) : g is a strong resolving function of G}. For any connected graph G of order n 2, we prove the sharp bounds 1 sdimf (G) n/2. Indeed, we show that sdimf (G) = 1 if and only if G is a path. If G contains a cut-vertex, then sdimf (G) n-1/2 is the sharp bound. We determine sdimf (G) when G is a tree, a cycle, a wheel, a complete k -partite graph, or the Petersen graph. For any tree T, we prove the sharp inequality sdimf (T + e) sdimf (T) and show that sdimf (G + e) - sdimf (G) can be arbitrarily large. Lastly, we furnish a Nordhaus-Gaddum-type result: Let G and (the complement of G) both be connected graphs of order n 4; it is readily seen that sdimf (G) + sdimf () = 2 if and only if n = 4; further, we characterize unicyclic graphs G attaining sdimf (G) + sdimf () = n. Springer International Publishing 2013.
