The metric dimension of a graph is the minimum number of landmarks needed to distinguish its vertices by their distance vectors. We study this invariant for the circulant graph $ C_n(1, 2, \ldots, t) $, equivalently the $ t $-th power of a cycle. For fixed $ t $, its metric dimension is known to be eventually periodic in $ n $ with period $ 2t $. Nevertheless, no exact formula was known for general $ t $ in either of the classes $ n\equiv0, 1\pmod{2t} $: The available lower and upper bounds remained separated by quantities linear in $ t $. For $ n\equiv0\pmod{2t} $, an earlier conjectured lower bound $ t+2 $ was subsequently proved, but it still did not meet the available upper bound. We close the gaps in both classes for every $ q\ge2 $ and $ t\ge1 $ by proving
$ \dim C_{2qt}(1, 2, \ldots, t) = \left\lceil\frac{4t}{3}\right\rceil, \qquad \dim C_{2qt+1}(1, 2, \ldots, t) = \left\lceil\frac{4t+2}{3}\right\rceil. $
The proofs use two different structural approaches. For $ n = 2qt $, a local counting argument gives the sharp lower bound, while a periodic construction based on antipodal landmark pairs attains it. For $ n = 2qt+1 $, an analysis of the gaps between consecutive landmarks yields the lower bound and leads to an explicit construction of matching size. Thus, our results turn the previously nonmatching bounds into exact formulas. Both values are independent of $ q $ and have the common leading term $ 4t/3 $, settling these two cases in the eventual periodic classification of this graph family.
Citation: Changhong Lu, Yuchun Xiong. Metric dimensions of circulant graphs $ C_n(1, 2, \ldots, t) $ for $ n\equiv0, 1\pmod{2t} $[J]. AIMS Mathematics, 2026, 11(11): 37270-37288. doi: 10.3934/math.20261441
The metric dimension of a graph is the minimum number of landmarks needed to distinguish its vertices by their distance vectors. We study this invariant for the circulant graph $ C_n(1, 2, \ldots, t) $, equivalently the $ t $-th power of a cycle. For fixed $ t $, its metric dimension is known to be eventually periodic in $ n $ with period $ 2t $. Nevertheless, no exact formula was known for general $ t $ in either of the classes $ n\equiv0, 1\pmod{2t} $: The available lower and upper bounds remained separated by quantities linear in $ t $. For $ n\equiv0\pmod{2t} $, an earlier conjectured lower bound $ t+2 $ was subsequently proved, but it still did not meet the available upper bound. We close the gaps in both classes for every $ q\ge2 $ and $ t\ge1 $ by proving
$ \dim C_{2qt}(1, 2, \ldots, t) = \left\lceil\frac{4t}{3}\right\rceil, \qquad \dim C_{2qt+1}(1, 2, \ldots, t) = \left\lceil\frac{4t+2}{3}\right\rceil. $
The proofs use two different structural approaches. For $ n = 2qt $, a local counting argument gives the sharp lower bound, while a periodic construction based on antipodal landmark pairs attains it. For $ n = 2qt+1 $, an analysis of the gaps between consecutive landmarks yields the lower bound and leads to an explicit construction of matching size. Thus, our results turn the previously nonmatching bounds into exact formulas. Both values are independent of $ q $ and have the common leading term $ 4t/3 $, settling these two cases in the eventual periodic classification of this graph family.
| [1] |
P. J. Slater, Leaves of trees, Congressus Numerantium, 14 (1975), 549–559. |
| [2] |
F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Comb., 2 (1976), 191–195. |
| [3] |
R. C. Tillquist, R. M. Frongillo, M. E. Lladser, Getting the lay of the land in discrete space: a survey of metric dimension and its applications, SIAM Rev., 65 (2023), 919–962. https://doi.org/10.1137/21M1409512 doi: 10.1137/21M1409512
|
| [4] |
K. Chau, S. Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math., 37 (2017), 509–534. https://doi.org/10.7494/OpMath.2017.37.4.509 doi: 10.7494/OpMath.2017.37.4.509
|
| [5] |
C. Grigorious, P. Manuel, M. Miller, B. Rajan, S. Stephen, On the metric dimension of circulant and Harary graphs, Appl. Math. Comput., 248 (2014), 47–54. https://doi.org/10.1016/j.amc.2014.09.045 doi: 10.1016/j.amc.2014.09.045
|
| [6] |
T. Vetrík, The metric dimension of circulant graphs, Can. Math. Bull., 60 (2017), 206–216. https://doi.org/10.4153/CMB-2016-048-1 doi: 10.4153/CMB-2016-048-1
|
| [7] |
T. Vetrík, On the metric dimension of directed and undirected circulant graphs, Discuss. Math. Graph Theor., 40 (2020), 67–76. https://doi.org/10.7151/dmgt.2110 doi: 10.7151/dmgt.2110
|
| [8] |
T. BC, S. Dueck, The metric dimension of circulant graphs, Opuscula Math., 45 (2025), 39–51. https://doi.org/10.7494/OpMath.2025.45.1.39 doi: 10.7494/OpMath.2025.45.1.39
|
| [9] |
R. Gao, Y. Xiao, Z. Zhang, On the metric dimension of circulant graphs, Can. Math. Bull., 67 (2024), 328–337. https://doi.org/10.4153/S0008439523000759 doi: 10.4153/S0008439523000759
|
| [10] |
C. Grigorious, T. Kalinowski, J. Ryan, S. Stephen, The metric dimension of the circulant graph $C(n, \pm\{1, 2, 3, 4\})$, Australas. J. Comb., 69 (2017), 417–441. |
| [11] |
M. Knor, R. Škrekovski, T. Vetrík, Metric dimension of circulant graphs with 5 consecutive generators, Mathematics, 12 (2024), 1384. https://doi.org/10.3390/math12091384 doi: 10.3390/math12091384
|
The case $t = 3m$
The case $t = 3m+1$
The case $t = 3m+2$
The landmark indices of $W^\star$ in one period. The right endpoint $n$ repeats $0$ to indicate the cyclic closure. The upper and lower rows correspond to $r = 1$ and $r\in\{q+1, 2q+1\}$, respectively