On the metric dimension of circulant and Harary graphs

Journal article


Grigorious, Cyriac, Manuel, Paul, Miller, Mirka, Rajan, Bharati and Stephen, Sudeep. (2014). On the metric dimension of circulant and Harary graphs. Applied Mathematics and Computation. 248, pp. 47-54. https://doi.org/10.1016/j.amc.2014.09.045
AuthorsGrigorious, Cyriac, Manuel, Paul, Miller, Mirka, Rajan, Bharati and Stephen, Sudeep
Abstract

A metric generator is a set W of vertices of a graph G(V, E) such that for every pair of vertices u; v of G, there exists a vertex w ϵ W with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. In this case the vertex w is said to resolve or distinguish the vertices u and v. The minimum cardinality of a metric generator for G is called the metric dimension. The metric dimension problem is to find a minimum metric generator in a graph G. In this paper, we make a significant advance on the metric dimension problem for circulant graphs C (n, ±{1, 2, . . . , j}), 1 ⩽ j ⩽ ⎿n/2⏌, n ⩾ 3, and Harary graphs.

KeywordsMetric basis ; Metric dimension ; Circulant graphs ; Harary graphs
Year01 Jan 2014
JournalApplied Mathematics and Computation
Journal citation248, pp. 47-54
PublisherAcademic Press (Elsevier)
ISSN0096-3003
Digital Object Identifier (DOI)https://doi.org/10.1016/j.amc.2014.09.045
Web address (URL)https://www.sciencedirect.com/science/article/pii/S0096300314012703?via%3Dihub
Research or scholarlyResearch
Page range47-54
Publisher's version
File Access Level
Controlled
Output statusPublished
Publication dates
Online14 Oct 2014
PrintDec 2014
Publication process dates
Deposited21 May 2024
Additional information

© 2014 Elsevier Inc. All rights reserved.

Place of publicationUnited States
Permalink -

https://acuresearchbank.acu.edu.au/item/907q1/on-the-metric-dimension-of-circulant-and-harary-graphs

Restricted files

Publisher's version

  • 10
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month
These values are for the period from 19th October 2020, when this repository was created.

Export as

Related outputs

Zero forcing in iterated line digraphs
Ferrero, Daniela, Kalinowski, Thomas and Stephen, Sudeep. (2019). Zero forcing in iterated line digraphs. Discrete Applied Mathematics. 255, pp. 198-208. https://doi.org/10.1016/j.dam.2018.08.019
Minimum rank and zero forcing number for butterfly networks
Ferrero, Daniela, Grigorious, Cyriac, Kalinowski, Thomas, Ryan, Joe and Stephen, Sudeep. (2019). Minimum rank and zero forcing number for butterfly networks. Journal of Combinatorial Optimization. 37(3), pp. 970-988. https://doi.org/10.1007/s10878-018-0335-1
A lower bound on the zero forcing number
Davila, Randy, Kalinowski, Thomas and Stephen, Sudeep. (2018). A lower bound on the zero forcing number. Discrete Applied Mathematics. 250, pp. 363-367. https://doi.org/10.1016/j.dam.2018.04.015
Average distance in interconnection networks via reduction theorems for vertex-weighted graphs
Klavžar, Sandi, Manuel, Paul, Nadjafi-Arani, M. J., Rajan, R. Sundara, Grigorious, Cyriac and Stephen, Sudeep. (2016). Average distance in interconnection networks via reduction theorems for vertex-weighted graphs. The Computer Journal. 59(12), pp. 1900-1910. https://doi.org/10.1093/comjnl/bxw046
Resolving-power dominating sets
Stephen, Sudeep, Rajan, Bharati, Grigorious, Cyriac and William, Albert. (2015). Resolving-power dominating sets. Applied Mathematics and Computation. 256, pp. 778-785. https://doi.org/10.1016/j.amc.2015.01.037
On the Strong Metric Dimension of Tetrahedral Diamond Lattice
Manuel, Paul, Rajan, Bharati, Grigorious, Cyriac and Stephen, Sudeep. (2015). On the Strong Metric Dimension of Tetrahedral Diamond Lattice. Mathematics in Computer Science. 9(2), pp. 201-208. https://doi.org/10.1007/s11786-015-0226-0
Power domination in certain chemical structures
Stephen, Sudeep, Rajan, Bharati, Ryan, Joe, Grigorious, Cyriac and William, Albert. (2015). Power domination in certain chemical structures. Journal of Discrete Algorithms (Amsterdam). 33, pp. 10-18. https://doi.org/10.1016/j.jda.2014.12.003
On the partition dimension of a class of circulant graphs
Grigorious, Cyriac, Stephen, Sudeep, Rajan, Bharati, Miller, Mirka and William, Albert. (2014). On the partition dimension of a class of circulant graphs. Information Processing Letters. 114(7), pp. 353-356. https://doi.org/10.1016/j.ipl.2014.02.005