The fractional metric dimension of permutation graphs
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 605461589 | ||
| 003 | CHVBK | ||
| 005 | 20210128100244.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 210128e20150301xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1007/s10114-015-4160-5 |2 doi |
| 035 | |a (NATIONALLICENCE)springer-10.1007/s10114-015-4160-5 | ||
| 100 | 1 | |a Yi |D Eunjeong |u Texas A&M University at Galveston, 77553, Galveston, TX, USA |4 aut | |
| 245 | 1 | 4 | |a The fractional metric dimension of permutation graphs |h [Elektronische Daten] |c [Eunjeong Yi] |
| 520 | 3 | |a 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 R G {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∈ U g(s). A real-valued function g: V (G) → [0, 1] is a resolving function of G if g(R G {x, y}) ≥ 1 for any two distinct vertices x, y ∈ V (G). The fractional metric dimension dim f (G) of a graph G is min{g(V (G)): g is a resolving function of G}. Let G 1 and G 2 be disjoint copies of a graph G, and let σ: V (G 1) → V (G 2) be a bijection. Then, a permutation graph G σ = (V, E) has the vertex set V = V (G 1) ∪ V (G 2) and the edge set E = E(G 1) ∪ E(G 2) ∪ {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 dim f (G σ) - 1 < ε. We give examples showing that neither is there a function h 1 such that dim f (G) < h 1(dim f (G σ)) for all pairs (G, σ), nor is there a function h 2 such that h 2(dim f (G)) > dim f (G σ)) for all pairs (G, σ). Furthermore, we investigate dim f (G σ)) when G is a complete k-partite graph or a cycle. | |
| 540 | |a Institute of Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Chinese Mathematical Society and Springer-Verlag Berlin Heidelberg, 2015 | ||
| 690 | 7 | |a Fractional metric dimension |2 nationallicence | |
| 690 | 7 | |a permutation graph |2 nationallicence | |
| 690 | 7 | |a tree |2 nationallicence | |
| 690 | 7 | |a complete k -partite graph |2 nationallicence | |
| 690 | 7 | |a cycle |2 nationallicence | |
| 773 | 0 | |t Acta Mathematica Sinica, English Series |d Institute of Mathematics, Chinese Academy of Sciences and Chinese Mathematical Society |g 31/3(2015-03-01), 367-382 |x 1439-8516 |q 31:3<367 |1 2015 |2 31 |o 10114 | |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10114-015-4160-5 |q text/html |z Onlinezugriff via DOI |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 900 | 7 | |a Metadata rights reserved |b Springer special CC-BY-NC licence |2 nationallicence | |
| 908 | |D 1 |a research-article |2 jats | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-springer | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1007/s10114-015-4160-5 |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 100 |E 1- |a Yi |D Eunjeong |u Texas A&M University at Galveston, 77553, Galveston, TX, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Acta Mathematica Sinica, English Series |d Institute of Mathematics, Chinese Academy of Sciences and Chinese Mathematical Society |g 31/3(2015-03-01), 367-382 |x 1439-8516 |q 31:3<367 |1 2015 |2 31 |o 10114 | ||