Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

On the Metric Dimension of Directed and Undirected Circulant Graphs

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
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 67-76
2083-5892
Język:
angielski
Prawa:
CC BY-NC-ND: Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0
Dostawca treści:
Biblioteka Nauki
Artykuł
  Przejdź do źródła  Link otwiera się w nowym oknie
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$.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies