Search

An e partition X of the vertex set V (H) of a connected graph H is the collection of e number of ordered disjoint subsets of V (H), denoted as X = {X1,X2>,: ::, Xe}. The representation of a vertex u is a distance vector r(ujX) = (d(u,X1), d(u,X2),: ::, d(u,Xe)), where d(u,Xi) is the distance of u from Xi. Any ordered e partition X is referred as resolving partition if representations of all the vertices are distinct. The smallest integer e is referred as the partition dimension of the graph. The advancement in the concept of partition dimension is fault-tolerant partition dimension where the representations are distinct at two places for each pair of vertices. In this paper, we compute the partition dimension and fault-tolerant partition dimension of some planar graphs. [ABSTRACT FROM AUTHOR] more...

Let Λ = {B1, B2, . . ., Bl} be an ordered l-partition of a connected graph G(V (G), E(G)). The partition representation of vertex x with respect to Λ is the l-vector, r(x|Λ) = (d(x, B1), d(x, B2), . . ., d(x, Bl)), where d(x, B) = min{d(x, y)|y ∈ B} is the distance between x and B. If the l - vectors r(x|Λ), for all x ∈ V (G) are distinct then l - partition is called a resolving partition. The least value of l for which there is a resolving l - partition is known as the partition dimension of G symbolized as pd(G). In this paper, the partition dimension of circulant graphs Cn(1, 2, 3, 4) is computed for n ≥ 8 as, pd(Cn(1, 2, 3, 4)) = { if 8 ≤ n ≤ 9; { 6, if n = 10; {5, if n ≥ 11. [ABSTRACT FROM AUTHOR] more...

The partition dimension is a variant of metric dimension in graphs. It has arising applications in the fields of network designing, robot navigation, pattern recognition and image processing. Let G (V (G) , E (G)) be a connected graph and Γ = {P1, P2, ..., Pm} be an ordered m-partition of V (G). The partition representation of vertex v with respect to Γ is an m-vector r (v|Γ) = (d (v, P1) , d (v, P2) , ..., d (v, Pm)), where d (v, P) = min {d (v, x) |x ∈ P} is the distance between v and P. If the m-vectors r (v|Γ) differ in at least 2 positions for all v ∈ V (G), then the m-partition is called a 2-partition generator of G. A 2-partition generator of G with minimum cardinality is called a 2-partition basis of G and its cardinality is known as the 2-partition dimension of G. Circulant graphs outperform other network topologies due to their low message delay, high connectivity and survivability, therefore are widely used in telecommunication networks, computer networks, parallel processing systems and social networks. In this paper, we computed partition dimension of circulant graphs Cn (1, 2) for n ≡ 2 (mod 4), n ≥ 18 and hence corrected the result given by Salman et al. [Acta Math. Sin. Engl. Ser. 2012, 28, 1851-1864]. We further computed the 2-partition dimension of Cn (1, 2) for n ≥ 6. [ABSTRACT FROM AUTHOR] more...

Fault-tolerant resolving partition is natural extension of resolving partitions which have many applications in different areas of computer sciences for example sensor networking, intelligent systems, optimization and robot navigation. For a nontrivial connected graph G (V (G) , E (G)), the partition representation of vertex v with respect to an ordered partition Π = {Si : 1 ≤ i ≤ k} of V (G) is the k-vector r (v | Π) = (d (v , S i)) i = 1 k , where, d (v, Si) = min {d (v, x) |x ∈ Si}, for i ∈ {1, 2, ..., k}. A partition Π is said to be fault-tolerant partition resolving set of G if r (u|Π) and r (v|Π) differ by at least two places for all u ≠ v ∈ V (G). A fault-tolerant partition resolving set of minimum cardinality is called the fault-tolerant partition basis of G and its cardinality the fault-tolerant partition dimension of G denoted by P (G). In this article, we will compute fault-tolerant partition dimension of families of tadpole and necklace graphs. [ABSTRACT FROM AUTHOR] more...

As a generalization of the concept of the partition dimension of a graph, this article introduces the notion of the k -partition dimension. Given a nontrivial connected graph G = (V , E) , a partition Π of V is said to be a k -partition generator of G if any pair of different vertices u , v ∈ V is distinguished by at least k vertex sets of Π, i.e., there exist at least k vertex sets S 1 , ... , S k ∈ Π such that d (u , S i) ≠ d (v , S i) for every i ∈ { 1 , ... , k }. A k -partition generator of G with minimum cardinality among all their k -partition generators is called a k -partition basis of G and its cardinality the k -partition dimension of G. A nontrivial connected graph G is k -partition dimensional if k is the largest integer such that G has a k -partition basis. We give a necessary and sufficient condition for a graph to be r -partition dimensional and we obtain several results on the k -partition dimension for k ∈ { 1 , ... , r }. [ABSTRACT FROM AUTHOR] more...

A partition Π = { S 1 , ... , S k } of the vertex set of a connected graph G is called a resolving partition of G if for every pair of vertices u and v , d (u , S j) ≠ d (v , S j) , for some part S j. The partition dimension β p (G) is the minimum cardinality of a resolving partition of G. A resolving partition Π is called resolving dominating if for every vertex v of G , d (v , S j) = 1 , for some part S j of Π. The dominating partition dimension η p (G) is the minimum cardinality of a resolving dominating partition of G. In this paper we show, among other results, that β p (G) ≤ η p (G) ≤ β p (G) + 1. We also characterize all connected graphs of order n ≥ 7 satisfying any of the following conditions: η p (G) = n , η p (G) = n − 1 , η p (G) = n − 2 and β p (G) = n − 2. Finally, we present some tight Nordhaus–Gaddum bounds for both the partition dimension β p (G) and the dominating partition dimension η p (G). [ABSTRACT FROM AUTHOR] more...

In this paper, we continue investigating the partition dimension for disconnected graphs. We determine the partition dimension for some classes of disconnected graphs G consisting of two components. If $$G=G_1 \cup G_2$$ , then we give the bounds of the partition dimension of G for $$G_1 = P_n$$ or $$G_1=C_n$$ and also for $$pd(G_1)=pd(G_2)$$ . [ABSTRACT FROM AUTHOR] more...

For a vertex v of a connected graph G (V, E) and a subset S of V, the distance between v and S is defined by d(v,S) = mind{d(v,x): x ∈ S}. For an ordered k-partition π = {S1, SS2, ...,S2..., S k} of V, the representation of v with respect to π is the k-vector r(v|π} = (d(v,S1), d(v,S2, ..., d (v,Sk. The k-partition π is a resolving partition if the k-vectors r(v|π ), v V∈ V are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. In this paper, we obtain the partition dimension of circulant graphs G - C (n, ± {1,2,...,j}), 1 < j <[n/2], n ≥ (j+k) (j+1) and n = k (mod 2j) as, Pd (G) = j + 1{when j is even and ged (k,2j) = 1,/when j is odd and k = 2m, 1 ≤ m ≤ j. [ABSTRACT FROM AUTHOR] more...

Abstract: Given an ordered partition of the vertex set of a connected graph , the partition representation of a vertex with respect to the partition is the vector , where represents the distance between the vertex and the set . A partition of is a resolving partition of if different vertices of have different partition representations, i.e., for every pair of vertices , . The partition dimension of is the minimum number of sets in any resolving partition of . In this paper we obtain several tight bounds on the partition dimension of trees. [Copyright &y& Elsevier] more...

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] more...

Abstract: Let G =(V, E) be a connected graph. The distance between two vertices u, v ∈ V, denoted by d(u, v), is the length of a shortest u − v path in G. The distance between a vertex v ∈ V and a subset P ⊂ V is defined as , and it is denoted by d(v, P). An ordered partition {P 1, P 2,…, P t } of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P 1), d(v, P 2),…, d(v, P t )) are different. The partition dimension of G, denoted by pd(G), is the minimum number of sets in any resolving partition of G. In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs G, H, pd(G × H)⩽ pd(G)+ pd(H) and pd(G × H)⩽ pd(G)+ dim(H), where dim(H) denotes the metric dimension of H. Consequently, we show that pd(G × H)⩽ dim(G)+ dim(H)+1. [Copyright &y& Elsevier] more...

Abstract: Let and be graphs where the set of vertices is the set of points of the integer lattice and the set of edges consists of all pairs of vertices whose city block and chessboard distances, respectively, are 1. In this paper it is shown that the partition dimensions of these graphs are 3 and 4, respectively, while their metric dimensions are not finite. Also, for every there exists an induced subgraph of of order with metric dimension n and partition dimension 3. These examples will answer a question raised by Chartrand, Salehi and Zhang. Furthermore, graphs of order having partition dimension are characterized, thus completing the characterization of graphs of order n having partition dimension 2, n, or given by Chartrand, Salehi and Zhang. The list of these graphs includes 23 members. [Copyright &y& Elsevier] more...