Translate this page into:
The metric dimension of the circulant graph with generators can be less than k
⁎Corresponding author. imrandhab@gmail.com (Muhammad Imran),
-
Received: ,
Accepted: ,
This article was originally published by Elsevier and was migrated to Scientific Scholar after the change of Publisher.
Peer review under responsibility of King Saud University.
Abstract
Circulant graphs are useful networks because of their symmetries. For and , the circulant graph consists of the vertices and the edges , where , and the subscripts are taken modulo n. The metric dimension of the circulant graphs for general k (and n) has been studied in several papers. In 2017, Chau and Gosselin proved that for every k, and they conjectured that if , where k is even and , then . We disprove both by showing that for every , there exists an such that . We conjecture that for cannot be less than .
Keywords
Metric dimension
Resolving set
Distance
Cayley graph
Circulant graph
1 Introduction
The metric dimension is an invariant which has applications in pharmaceutical chemistry (see Chartrand et al., 2000), pattern recognition and image processing (see Melter and Tomescu, 1984), robot navigation (see Khuller et al., 1996), and Sonar and coast guard Loran (see Slater, 1975).
In a graph G having vertex set , the number of edges in a shortest path connecting two vertices is the distance between u and v. If , then a vertex w resolves two vertices u and v. For an ordered set , the ordered z-tuple is the representation of distances of v in terms of W. If all the vertices of G have different representations, then is a resolving set of G. The metric dimension is the number of vertices in a smallest resolving set.
Circulant graphs are very useful networks because of their symmetries. For and , the circulant graph has the vertices and the edges , where , and the subscripts are taken modulo n. We assume that , because for would contain multiple edges. So, is the set of generators of .
In this paper, we focus on the following question: For a fixed k, find
By Borchert and Gosselin (2018) and Javaid et al. (2008), we have
By Borchert and Gosselin (2018) and Imran et al. (2012), for
,
Since
and
, Grigorious et al. (2014) assumed and proved that
. Their result does not hold. In Vetrík (2017) it was proved that
can be k, and that for
where
,
and for
where
and
, we have
Chau and Gosselin (2017) obtained several strong results, but their inequality (1) is incorrect. They proved that for
,
Let us note that the graphs were studied in Javaid et al. (2012), in Azhar and Javaid (2018), in Du Toit and Vetrík (2019), for even n in Salman et al. (2012), in Imran and Bokhary (2014), in Imran et al. (2018), in Grigorious et al. (2017) and Vetrík (2017), also in Vetrík (2020), and some interesting networks were investigated also in Arulperumjothi et al. (2023), Azeem et al. (2022), Koam et al. (2022), Prabhu et al. (2022) and Prabhu et al. (2022).
2 New bounds
We show that for every , there exists an n such that . The case is studied in Theorem 1, is studied in Theorem 2, is investigated in Theorem 3, is considered in Theorem 4 and is studied in Theorem 5. Note that the subscripts of the vertices are taken modulo n.
Let where such that . Then
Let . We have , so for any vertex (where or 0), there are 4 vertices at distance 2 from (and vertices at distance 1 from ). Let . It follows that the representations of a vertex of and a vertex of are not the same in terms of W.
For the vertices of where and the ordered set , we get Since for , and for , the vertices of are resolved (for ). We have Note that . Finally, we need to resolve . We have and Thus all the vertices of are resolved. So, W is a resolving set and we obtain . □
Let where such that . Then
For , let . We show that resolves . We have , so for any vertex where , there are 7 vertices at distance 2 from (and vertices at distance 1 from ). Thus there are exactly 7 vertices at distance 2 from where . Those vertices are the vertices of the set So, the representations of a vertex of and a vertex of are not the same in terms of W. For the vertices of and , we get The vertices , so the vertices of are resolved (where ). Since , the set W resolves the vertices of . Therefore . □
Let where such that . Then
For , let . We show that resolves . We have , so for any vertex where , there are 5 vertices at distance 2 from . For each where , there are 7 vertices at distance 2 from at least one of . Those vertices are the vertices of the set So, the representations of a vertex of and a vertex of are not the same in terms of W. For the vertices of and the ordered set , we get The vertices , so the vertices of are resolved (where ). Since , W resolves the vertices of . Therefore . □
Let where such that . Then
For , let and . Let and Note that . We prove that W resolves . We have , so for any vertex where , there are 5 vertices at distance 2 from .
For each where , there are exactly 7 vertices at distance 2 from at least one of . Those vertices are the vertices of the set So, the representations of a vertex in and a vertex of are not the same in terms of W. For the vertices of where in terms of the ordered set , we get The vertices , so the vertices of are resolved by W (where ).
Similarly, for each where , there are exactly 7 vertices at distance 2 from at least one of . Those vertices are the vertices of the set So, the representations of a vertex of and a vertex of are not the same in terms of W. For the vertices of where in terms of the ordered set , we get The vertices , so the vertices of are resolved (where ).
We have and Finally, we resolve the vertices Note that and Thus all the vertices of are resolved. So . □
The proof of Theorem 5 is longer than the previous proofs, because the resolving sets used in the proof of Theorem 5 are not as simple as resolving sets used in the previous proofs.
Let where such that . Then
For , let . For , let . Let and Note that . We prove that W resolves . We have , so for any vertex where , there are 5 vertices at distance 2 from .
For each where , there are 7 vertices at distance 2 from at least one of . Those vertices are the vertices of the set So, the representations of a vertex of and a vertex of are not the same in terms of W. For the vertices in and the ordered set , we get The vertices , so the vertices of are resolved by W (where ).
Similarly, for each where , there are 7 vertices at distance 2 from at least one of . Those vertices are the vertices of the set For the vertices of and the ordered set , we get The vertices , so the vertices of are resolved.
We have and Finally, we resolve the vertices if , and it remains to resolve all the vertices if . Note that so those vertices are resolved. We obtain and For , we obtain and for , Thus all the vertices of are resolved for .
If , it remains to consider and . We have and It can be seen above that no other vertex has such representation in terms of the ordered sets and . So, W resolves all the vertices of . Thus . □
From Theorems 1–5, we obtain the following corollary.
For every , there exists an such that
Let us note that for and 8, we have , so Corollary 1 is important for .
3 Concluding remarks and further work
We showed that for every , there is an such that . The importance of this result is that it has not been known before that can be less than k. We believe that cannot be less than for , thus we provide Conjecture 1 as a possible future work. Note that , otherwise would contain multiple edges.
For every (and ),
Conjecture 1 would not hold for and . For example, for and , the set is one possible resolving set of .
Data availability statement
The data used to find the results are included in this paper.
Author contributions
All the authors contributed equally to this work. All the authors read and approved the final version.
Acknowledgements
The work of T. Vetrík is based on the research supported by DSI-NRF Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS), South Africa. Opinions expressed and conclusions arrived at are those of the author and are not necessarily to be attributed to the CoE-MaSS. The work of M. Imran is supported by Asian Universities Alliance (AUA) grant of United Arab Emirates University (Grant No. G00003461). R. Škrekovski and M. Knor acknowledge partial support of the Slovenian research agency ARRS program P1-0383 and ARRS project J1-3002. M. Knor aknowledges partial support by Slovak research grants VEGA 1/0206/20, VEGA 1/0567/22, APVV-17-0428, APVV-19-0308.
Declaration of Competing Interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
References
- Redefining fractal cubic networks and determining their metric dimension and fault-tolerant metric dimension. Appl. Math. Comput.. 2023;452:128037.
- [Google Scholar]
- Sharp bounds on partition dimension of hexagonal Möbius ladder. J. King Saud Univ. Sci.. 2022;34(2):101779.
- [Google Scholar]
- The metric dimension of circulant graphs and Cayley hypergraphs. Util. Math.. 2018;106:125-147.
- [Google Scholar]
- Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math.. 2000;105(1–3):99-113.
- [Google Scholar]
- The metric dimension of circulant graphs and their Cartesian products. Opuscula Math.. 2017;37(4):509-534.
- [Google Scholar]
- On the metric dimension of circulant graphs with 2 generators. Kragujevac J. Math.. 2019;43(1):49-58.
- [Google Scholar]
- The metric dimension of the circulant graph . Australas. J. Combin.. 2017;69(3):417-441.
- [Google Scholar]
- On the metric dimension of circulant and Harary graphs. Appl. Math. Comput.. 2014;248:47-54.
- [Google Scholar]
- On the metric dimension and diameter of circulant graphs with three jumps. Discrete Math. Algorithms Appl.. 2018;10(1):1850008.
- [Google Scholar]
- On resolvability in double-step circulant graphs, U.P.B. Sci. Bull. Series A. 2014;76(2):31-42.
- [Google Scholar]
- Metric dimension and determining number of Cayley graphs. World Appl. Sci. J.. 2012;18:1800-1812.
- [Google Scholar]
- Families of regular graphs with constant metric dimension. Util. Math.. 2008;75:21-33.
- [Google Scholar]
- Computation of vertex and edge resolvability of benzenoid tripod structure. J. King Saud Univ. Sci.. 2022;34(6):102208.
- [Google Scholar]
- Metric bases indigital geometry. Comput. Vision Graphics Image Process.. 1984;25:113-121.
- [Google Scholar]
- Resolving-power domination number of probabilistic neural networks. J. Intell. Fuzzy Syst.. 2022;43(5):6253-6263.
- [Google Scholar]
- Twin vertices in fault-tolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks. Appl. Math. Comput.. 2022;420:126897.
- [Google Scholar]
- Resolvability in circulant graphs. Acta Math. Sin. (Engl. Ser.). 2012;28(9):1851-1864.
- [Google Scholar]
- On the metric dimension of directed and undirected circulant graphs. Discuss. Math. Graph Theory. 2020;40(1):67-76.
- [Google Scholar]
- On the metric dimension of circulant graphs with 4 generators. Contrib. Discrete Math.. 2017;12(2):104-114.
- [Google Scholar]
Appendix A
Supplementary material
Supplementary data associated with this article can be found, in the online version, at https://doi.org/10.1016/j.jksus.2023.102834.
Supplementary material
The following are the Supplementary data to this article: