- Tytuł:
- The metric dimension of circulant graphs and their Cartesian products
- Autorzy:
-
Chau, K.
Gosselin, S. - Powiązania:
- https://bibliotekanauki.pl/articles/255804.pdf
- Data publikacji:
- 2017
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
metric dimension
circulant graph
Cartesian product - Opis:
- Let G = (V, E) be a connected graph (or hypergraph) and let d(x,y) denote the distance between vertices x,y ∈V(G). A subset W ⊆V(G) is called a resolving set for G if for every pair ol distinct vertices x, y ∈ (G), there is w ∈W such that d(x,w) ≠d(y,w). The minimum cardinality of a resolving set for G is called the metric dimension of G, denoted by β (G). The circulant graph Cn(l, 2,... , t) has vertex set {v0, v1 …, vn-1} and edges [formula] where 0 ≤ i ≤ n — 1 and 1 ≤j ≤ t and the indices are taken modulo [formula]. In this paper we determine the exact metric dimension olthe circulant graphs Cn(l, 2,... , t). extending previous results due to Borchert and Gosselin (2013), Grigorious et al. (2014), and Vetrik (2016). In particular, we show that [formula] for large enough n, which implies that the metric dimension ol these circulants is completely determined by the congruence class ol n modulo 2t. We determine the exact value of β Cn (l, 2,.. . , i)) for n ≡ 2 mod 2t and n =≡ (t + 1) mod 2t and we give better bounds on the metric dimension ol these circulants for n ≡ 0 mod 2t and n ≡ 1 mod 2t. In addition, we bound the metric dimension ol Cartesian products ol circulant graphs.
- Źródło:
-
Opuscula Mathematica; 2017, 37, 4; 509-534
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł