The Fractional Strong Metric Dimension of Graphs Conference Paper uri icon


  • 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.

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Kang, C. X., & Yi, E.

citation count

  • 16

complete list of authors

  • Kang, Cong X||Yi, Eunjeong

publication date

  • January 2013