Loading...
Please wait, while we are loading the content...
Similar Documents
The fractional metric dimension of permutation graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Yi, Eunjeong |
| Copyright Year | 2015 |
| Abstract | AbstractLet 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 $1 < \dim _f (G_\sigma ) \leqslant \tfrac{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. |
| Starting Page | 367 |
| Ending Page | 382 |
| Page Count | 16 |
| File Format | PDF HTM / HTML |
| DOI | 10.1007/s10114-015-4160-5 |
| Volume Number | 31 |
| Alternate Webpage(s) | https://page-one.springer.com/pdf/preview/10.1007/s10114-015-4160-5 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
