摘要
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 equa l 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 graph Gσ =（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 1 〈 dimf（Gσ） ≤1/2（｜V（G）｜ ＋ ｜S（G）｜） 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.
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 equa l 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 graph Gσ =（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 1 〈 dimf（Gσ） ≤1/2（｜V（G）｜ ＋ ｜S（G）｜） 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.
