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 ) = Σx∈U 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

  • 13

complete list of authors

  • Kang, Cong X||Yi, Eunjeong

publication date

  • January 2013