The metric dimension of the circulant graph with 2k generators can be less than k
Circulant graphs are useful networks because of their symmetries. For k⩾2 and n⩾2k+1, the circulant graph Cn(1,2,…,k) consists of the vertices v0,v1,v2,…,vn-1 and the edges vivi+1,vivi+2,…,vivi+k, where i=0,1,2,…,n-1, and the subscripts are taken modulo n. The metric dimension β(Cn(1,2,…,k)) of the...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2023-10-01
|
| Series: | Journal of King Saud University: Science |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1018364723002963 |
| _version_ | 1797687692753895424 |
|---|---|
| author | Tomáš Vetrík Muhammad Imran Martin Knor Riste Škrekovski |
| author_facet | Tomáš Vetrík Muhammad Imran Martin Knor Riste Škrekovski |
| author_sort | Tomáš Vetrík |
| collection | DOAJ |
| description | Circulant graphs are useful networks because of their symmetries. For k⩾2 and n⩾2k+1, the circulant graph Cn(1,2,…,k) consists of the vertices v0,v1,v2,…,vn-1 and the edges vivi+1,vivi+2,…,vivi+k, where i=0,1,2,…,n-1, and the subscripts are taken modulo n. The metric dimension β(Cn(1,2,…,k)) of the circulant graphs Cn(1,2,…,k) for general k (and n) has been studied in several papers. In 2017, Chau and Gosselin proved that β(Cn(1,2,…,k))⩾k for every k, and they conjectured that if n=2k+r, where k is even and 3⩽r⩽k-1, then β(Cn(1,2,…,k))=k. We disprove both by showing that for every k⩾9, there exists an n∈[2k+5,2k+8]⊂[2k+3,3k-1] such that β(Cn(1,2,…,k))⩽2k3+2. We conjecture that for k⩾6,β(Cn(1,2,…,k)) cannot be less than 2k3+2. |
| first_indexed | 2024-03-12T01:21:21Z |
| format | Article |
| id | doaj.art-451e1c61693046e79e41b87e45a1d68a |
| institution | Directory Open Access Journal |
| issn | 1018-3647 |
| language | English |
| last_indexed | 2024-03-12T01:21:21Z |
| publishDate | 2023-10-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Journal of King Saud University: Science |
| spelling | doaj.art-451e1c61693046e79e41b87e45a1d68a2023-09-13T04:24:46ZengElsevierJournal of King Saud University: Science1018-36472023-10-01357102834The metric dimension of the circulant graph with 2k generators can be less than kTomáš Vetrík0Muhammad Imran1Martin Knor2Riste Škrekovski3Department of Mathematics and Applied Mathematics, University of the Free State, Bloemfontein, South AfricaDepartment of Mathematical Sciences, Colleges of Science, United Arab Emirates University, Al Ain, United Arab Emirates; Corresponding author.Slovak University of Technology, Bratislava, SlovakiaFaculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia; Faculty of Information Studies, Novo Mesto, SloveniaCirculant graphs are useful networks because of their symmetries. For k⩾2 and n⩾2k+1, the circulant graph Cn(1,2,…,k) consists of the vertices v0,v1,v2,…,vn-1 and the edges vivi+1,vivi+2,…,vivi+k, where i=0,1,2,…,n-1, and the subscripts are taken modulo n. The metric dimension β(Cn(1,2,…,k)) of the circulant graphs Cn(1,2,…,k) for general k (and n) has been studied in several papers. In 2017, Chau and Gosselin proved that β(Cn(1,2,…,k))⩾k for every k, and they conjectured that if n=2k+r, where k is even and 3⩽r⩽k-1, then β(Cn(1,2,…,k))=k. We disprove both by showing that for every k⩾9, there exists an n∈[2k+5,2k+8]⊂[2k+3,3k-1] such that β(Cn(1,2,…,k))⩽2k3+2. We conjecture that for k⩾6,β(Cn(1,2,…,k)) cannot be less than 2k3+2.http://www.sciencedirect.com/science/article/pii/S1018364723002963Metric dimensionResolving setDistanceCayley graphCirculant graph |
| spellingShingle | Tomáš Vetrík Muhammad Imran Martin Knor Riste Škrekovski The metric dimension of the circulant graph with 2k generators can be less than k Journal of King Saud University: Science Metric dimension Resolving set Distance Cayley graph Circulant graph |
| title | The metric dimension of the circulant graph with 2k generators can be less than k |
| title_full | The metric dimension of the circulant graph with 2k generators can be less than k |
| title_fullStr | The metric dimension of the circulant graph with 2k generators can be less than k |
| title_full_unstemmed | The metric dimension of the circulant graph with 2k generators can be less than k |
| title_short | The metric dimension of the circulant graph with 2k generators can be less than k |
| title_sort | metric dimension of the circulant graph with 2k generators can be less than k |
| topic | Metric dimension Resolving set Distance Cayley graph Circulant graph |
| url | http://www.sciencedirect.com/science/article/pii/S1018364723002963 |
| work_keys_str_mv | AT tomasvetrik themetricdimensionofthecirculantgraphwith2kgeneratorscanbelessthank AT muhammadimran themetricdimensionofthecirculantgraphwith2kgeneratorscanbelessthank AT martinknor themetricdimensionofthecirculantgraphwith2kgeneratorscanbelessthank AT risteskrekovski themetricdimensionofthecirculantgraphwith2kgeneratorscanbelessthank AT tomasvetrik metricdimensionofthecirculantgraphwith2kgeneratorscanbelessthank AT muhammadimran metricdimensionofthecirculantgraphwith2kgeneratorscanbelessthank AT martinknor metricdimensionofthecirculantgraphwith2kgeneratorscanbelessthank AT risteskrekovski metricdimensionofthecirculantgraphwith2kgeneratorscanbelessthank |