- Title
- On the metric dimension of circulant and Harary graphs
- Creator
- Grigorious, Cyriac; Manuel, Paul; Miller, Mirka; Rajan, Bharati; Stephen, Sudeep
- Relation
- Applied Mathematics and Computation Vol. 248, p. 47-54
- Publisher Link
- http://dx.doi.org/10.1016/j.amc.2014.09.045
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2014
- Description
- 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 for Harary graphs.
- Subject
- metric basis; metric dimension; circulant graphs; Harary graphs
- Identifier
- http://hdl.handle.net/1959.13/1297367
- Identifier
- uon:19436
- Identifier
- ISSN:0096-3003
- Language
- eng
- Reviewed
- Hits: 844
- Visitors: 984
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|