Search

The size of a resolving set R of a non-trivial connected graph Γ of order n ≥ 2 is the number of edges in the induced subgraph < R >. The minimum cardinality of a resolving set of size k of graph Γ is called the metric dimension of size k, denoted by β(k) (Γ). We study the existence of resolving sets of size k in some families of graphs and investigate their properties. We find bounds on the metric dimension of size k of a graph Γ. We give the necessary condition for the metric dimension of size k and size (k + 1) of a graph Γ, to satisfy the inequality β(k+1)(Γ)-β(k) (Γ) ≤ 1. We will disprove a conjecture on bounds of the metric dimension of size k. For every positive integers k, l, and n such that k + 1 ≤ l ≤ n, we give a realizable result of a graph Γ of order n and l = β(k) (Γ). [ABSTRACT FROM AUTHOR]

A familyGof connected graphs is said to be a family with constant metric dimension if its metric dimension is finite and does not depend upon the choice ofGinG.In this paper, we study the metric dimension of the generalized Petersen graphsP(2m, m −1) and give a partial answer to an open problem raised in [13]: Is the generalized Petersen graphsP(s, t), fors ≥7 and 3≤ t ≤, a family of graphs with constant metric dimension? We prove that the generalized Petersen graphsP(2m, m −1) have metric dimension equal to 3 for all oddm ≥3, and equal to 4 for all evenm ≥4. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of the arithmetic graph of a composite number m, denoted by A m . It has been observed that there exist different composite numbers for which the arithmetic graphs are isomorphic. It is proved that the maximum distance between any two vertices of A m is two or three. Conditions under which the vertices have the same degrees and neighborhoods have also been identified. Symmetric behavior of the vertices lead to the study of the metric dimension of A m which gives minimum cardinality of vertices to distinguish all vertices in the graph. We give exact formulae for the metric dimension of A m , when m has exactly two distinct prime divisors. Moreover, we give bounds on the metric dimension of A m , when m has at least three distinct prime divisors. [ABSTRACT FROM AUTHOR]

Abstract: Let be a connected graph and be the distance between the vertices and in . A subset of vertices is called a resolving set or locating set for if for every two distinct vertices , there is a vertex such that for . A resolving set containing the minimum number of vertices is called a metric basis for and the number of vertices in a metric basis is its metric dimension, denoted by . Let be a family of connected graphs depending on as follows: the order and . If there exists a constant such that for every then we shall say that has bounded metric dimension. The metric dimension of a class of circulant graphs has been determined by Javaid and Rahim (2008) . In this paper, we extend this study to an infinite class of circulant graphs . We prove that the circulant graphs have metric dimension equal to 4 for . For only 5 vertices appropriately chosen suffice to resolve all the vertices of , thus implying that except when . [Copyright &y& Elsevier]