- Tytuł:
- On the Metric Dimension of Directed and Undirected Circulant Graphs
- Autorzy:
- Vetrík, Tomáš
- Powiązania:
- https://bibliotekanauki.pl/articles/31870010.pdf
- Data publikacji:
- 2020-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
metric dimension
resolving set
circulant graph
distance - Opis:
- The undirected circulant graph $C_n(±1, ±2, . . ., ±t)$ consists of vertices $v_0, v_1, . . ., v_{n−1}$ and undirected edges $v_iv_{i+j}$, where $0 ≤ i ≤ n − 1, 1 ≤ j ≤ t (2 ≤ t ≤ \frac{n}{2})$, and the directed circulant graph $C_n(1, t)$ consists of vertices $v_0, v_1, . . ., v_{n−1}$ and directed edges $v_iv_{i+1}, v_iv_{i+t}$, where $0 ≤ i ≤ n − 1 (2 ≤ t ≤ n−1)$, the indices are taken modulo $n$. Results on the metric dimension of undirected circulant graphs $C_n(±1, ±t)$ are available only for special values of $t$. We give a complete solution of this problem for directed graphs $C_n(1, t)$ for every $t ≥ 2$ if $n ≥ 2t^2$. Grigorious et al. [On the metric dimension of circulant and Harary graphs, Appl. Math. Comput. 248 (2014) 47–54] presented a conjecture saying that dim $(C_n(±1, ±2, . . ., ±t)) = t + p − 1$ for $n = 2tk + t + p$, where $3 ≤ p ≤ t + 1$. We disprove it by showing that dim $(C_n(±1, ±2, . . ., ±t)) ≤ t + \frac{p+1}{2}$ for $n = 2tk + t + p$, where $t ≥ 4$ is even, $p$ is odd, $1 ≤ p ≤ t + 1$ and $k ≥ 1$.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 67-76
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł