The Fractional Strong Metric Dimension of Graphs

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 ∈ Ug(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, sdim _f (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 \le sdim_f(G) \le \frac{n}{2}\). Indeed, we show that sdim _f (G) = 1 if and only if G is a path. If G contains a cut-vertex, then \(sdim_f(G) \le \frac{n-1}{2}\) is the sharp bound. We determine sdim _f (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 sdim _f (T + e) ≥ sdim _f (T) and show that sdim _f (G + e) − sdim _f (G) can be arbitrarily large. Lastly, we furnish a Nordhaus-Gaddum-type result: Let G and \(\overline{G}\) (the complement of G) both be connected graphs of order n ≥ 4; it is readily seen that \(sdim_f(G)+sdim_f(\overline{G})=2\) if and only if n = 4; further, we characterize unicyclic graphs G attaining \(sdim_f(G)+sdim_f(\overline{G})=n\).

Authors and Affiliations

1. Texas A&M University at Galveston, Galveston, TX, 77553, USA

   Cong X. Kang & Eunjeong Yi

Editors and Affiliations

1. Institute of Theoretical Computer Science, ETH Zürich, Zürich, Switzerland

   Peter Widmayer

2. State Key Lab for Manufacturing Systems Engineering, 710049, Xi’an, China

   Yinfeng Xu

3. Department of Computer Science, Montana State University, 59717-3880, Bozeman, MT, USA

   Binhai Zhu

Reprints and permissions

© 2013 Springer International Publishing Switzerland

Policies and ethics