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
Informacja
SZANOWNI CZYTELNICY!
UPRZEJMIE INFORMUJEMY, ŻE BIBLIOTEKA FUNKCJONUJE W NASTĘPUJĄCYCH GODZINACH:
Wypożyczalnia i Czytelnia Główna: poniedziałek – piątek od 9.00 do 19.00