On the metric dimension of directed and undirected circulant graphs (Q2282465): Difference between revisions

A vertex \(w\) resolves two vertices \(u\) and \(v\) if \(d(u, w) \neq d(v, w)\). For an ordered set of vertices \(W = \{w_1, w_2,\dots, w_z\}\), the representation of distances of \(v\) with respect to \(W\) is the ordered \(z\)-tuple \(r(v|W) = d(v, w_1), d(v, w_2), \dots, d(v, w_z)\). A set \(W \subseteq V(G)\) is a resolving set of \(G\) if every two distinct vertices of \(G\) have different representations of distances with respect to \(w\). The metric dimension of \(G\) is the number of vertices in a smallest resolving set and it is denoted by \(\dim(G)\). Let \(n\), \(m\) and \(a_1, a_2, \dots , a_m\) be positive integers such that \(1 \leq a_1 < a_2 < \dots < a_m \leq \frac{n}{2}\) . The undirected circulant graph \(C_n(\pm a_1, \pm a_2,\dots , \pm a_m)\) consists of the vertices \(v_0, v_1, \dots, v_{n-1}\) and undirected edges \(v_iv_{i+a_j}\) , where \(0 \leq i \leq n - 1\), \(1 \leq j \leq m\); the indices are taken modulo \(n\). For generators \(a_1, a_2, \dots , a_m\) such that \(1 \leq a_1 < a_2 < \dots < a_m \leq n-1\), the directed circulant graph \(C_n(a_1, a_2, \dots , a_m)\) consists of the vertices \(v_0, v_1,\dots , v_{n-1}\) and directed edges \(v_iv_{i+a_j}\), where \(0 \leq i \leq n - 1\), \(1 \leq j \leq m\); the indices are taken modulo \(n\). The directed circulant graph \(C_n(-a_1,-a_2, \dots ,-a_m)\) contains the directed edges \(v_iv_{i-a_j}\). In the case of directed circulant graphs, the authors proved the following: \par 1.) Let \(t \geq 2\) and \(n \geq 2t^2\). Then \(\dim C_n(-1,-t)\geq t\). \par 2.) Let \(2 \leq t < n\). Then \(\dim C_n(-1,-t) \leq t\). The result for undirected circulant graphs is the following: Let \(n = 2tk + t + p\), where \(t \geq 4\) is even, \(p\) is odd, \( 1 \leq p \leq t + 1\) and \(k \geq 1\). Then \(\dim (C_n(\pm 1, \pm 2,\dots , \pm t)) \leq t + \frac{p+1}{2}\).