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]

A vertexvof a connected graphGdistinguishes a pairu, wof vertices ofGifd(v, u)≠d(v, w), whered(·,·) denotes the length of a shortest path between two vertices inG. Ak-partition Π={S1,S2, …,Sk} of the vertex set ofGis said to be a locatic partition if for every pair of distinct verticesvandwofG, there exists a vertexs∈Sifor all 1≤i≤kthat distinguishesvandw. The cardinality of a largest locatic partition is called the locatic number ofG. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of ordernhaving locatic numbern, n−1 andn−2. Some realizable results are also given in this paper. [ABSTRACT FROM AUTHOR]

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, υ ∈ V ( G) there is a vertex w ∈ W such that d( u,w) ≠ d( υ,w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim( G). For a vertex u of G and a subset S of V ( G), the distance between u and S is the number min d( u, s). A k-partition Π = { S, S, ..., S} of V ( G) is called a resolving partition if for every two distinct vertices u, v ∈ V ( G) there is a set S in Π such that d( u, S) ≠ d( v, S). The minimum k for which there is a resolving k-partition of V ( G) is called the partition dimension of G, denoted by pd( G). The circulant graph is a graph with vertex set ℤ, an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i − j (mod n) ∈ C, where C ∈ ℤ has the property that C = −C and 0 ∉ C. The circulant graph is denoted by X where Δ = | C|. In this paper, we study the metric dimension of a family of circulant graphs X with connection set $$C = \left\{ {1,\tfrac{n} {2},n - 1} \right\}$$ and prove that dim( X) is independent of choice of n by showing that We also study the partition dimension of a family of circulant graphs X with connection set C = {±1,±2} and prove that pd( X) is independent of choice of n and show that pd( X) = 5 and . [ABSTRACT FROM AUTHOR]