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 ) = Σ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 cutvertex, then sdimf (G) ≤ n1/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 NordhausGaddumtype 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)
citation count
complete list of authors

Kang, Cong XYi, Eunjeong
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
International Standard Book Number (ISBN) 13
Additional Document Info
start page
end page
volume