The fractional metric dimension of permutation graphs
Academic Article
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
2015, Institute of Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Chinese Mathematical Society and Springer-Verlag Berlin Heidelberg. Let G = (V (G),E(G)) be a graph with vertex set V (G) and edge set E(G). For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equal to the distance from y to z in G. For a function g defined on V (G) and for U V (G), let g(U) = s Ug(s). A real-valued function g: V (G) [0, 1] is a resolving function of G if g(RG{x, y}) 1 for any two distinct vertices x, y V (G). The fractional metric dimension dimf (G) of a graph G is min{g(V (G)): g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let : V (G1) V (G2) be a bijection. Then, a permutation graphG = (V, E) has the vertex set V = V (G1) V (G2) and the edge set E = E(G1) E(G2) {uv | v = (u)}. First, we determine dimf (T) for any tree T. We show that (Formula Presented) for any connected graph G of order at least 3, where S(G) denotes the set of support vertices of G. We also show that, for any > 0, there exists a permutation graph G such that dimf(G) - 1 < . We give examples showing that neither is there a function h1 such that dimf(G) < h1(dimf (G)) for all pairs (G, ), nor is there a function h2 such that h2(dimf (G)) > dimf(G)) for all pairs (G, ). Furthermore, we investigate dimf(G)) when G is a complete k-partite graph or a cycle.