Search

Partition dimension problems involve dividing a graph's vertex set into a minimum number of disjoint sets so that each vertex is different with respect to the representation from each disjoint set. As a result of the development of this method, a number of applications have arisen in a number of fields such as drug design, navigation of robots, pattern recognition, and image processing. In this paper, we have calculated the partition dimension of oxide and zigzag benzenoid networks, and the subdivision of benzenoid hydrocarbon and triangular benzene networks. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. For a vertex v of G and a subset S of V(G), the distance between v and S is d(v, S) = min Given an ordered k-partition = of V(G), the representation of v with respect to is the k-vector If for each pair of distinct vertices then the k-partition is said to be a resolving partition. The partition dimension of G, denoted by pd(G), is determined by the minimum k for which there is a resolving partition of V(G). If each induced subgraph for Si, is connected in G, then the resolving partition = of V(G) is said to be connected. The connected partition dimension of G, denoted by cpd(G), is determined by the minimum k for which there is a connected resolving partition of V(G). In this paper, we compute the connected partition dimension of the truncated wheels TWn. It is shown that for any natural number the connected partition dimension of the truncated wheel TWn is 3 when n = 3 and when

Let $\Omega $ be a connected graph and for a given $l$ -ordered partition of vertices of a connected graph $\Omega $ is represented as $\beta =\{\beta _{1},\beta _{2}, {\dots },\beta _{l}\}$ . The representation of a vertex $\mu \in V(\Omega)$ is the vector $r(\mu |\beta)=(d(\mu,\beta _{1}),d(\mu,\beta _{2}), {\dots }, d(\mu,\beta _{l}))$ . The partition $\beta $ is a resolving partition for vertices of $\Omega $ if all vertices of $\Omega $ having the unique representation with respect to $\beta $ . The minimum number of $l$ in the resolving partition for $\Omega $ is known as the partition dimension of $\Omega $ and represented as $pd(\Omega)$ . Resolving partition and partition dimension have multipurpose applications in networking, optimization, computer, mastermind games and modeling of chemical structures. The problem of computing constant values of partition dimension is NP-hard so one can find sharp bound for the partition dimension of graph. In this article, we computed the upper bound for the convex polytopes $\mathbb {E}_{n},~\mathbb {S}_{n},~\mathbb {T}_{n},~\mathbb {G}_{n},~\mathbb {Q}_{n}$ and flower graph $f_{n\times 3}$ .

Finding the partition dimension of a graph is one of the interesting (and uncompletely solved) problems of graph theory. For instance, the values of the partition dimensions for most kind of trees are still unknown. Although for several classes of trees such as paths, stars, caterpillars, homogeneous firecrackers and others, we do know their partition dimensions. In this paper, we determine the partition dimension of a subdivision of a particular tree, namely homogeneous firecrackers. Let G be any graph. For any positive integer k and e ∈ E(G), a subdivision of a graph G, denoted by S(G(e; k)), is the graph obtained from G, by replacing an edge e with a (k + 1)-path. We show that the partition dimension of S(G(e; k)) is equal to the partition dimension of G, if G, is a homogeneous firecracker. [ABSTRACT FROM AUTHOR]

For a graph G=(V,E), a partition Ω=\{O_1,O_2,…,O_k \} of the vertex set V is called a resolving partition if every pair of vertices u,v∈V(G) have distinct representations under Ω. The partition dimension of G is the minimum integer k such that G has a resolving k-partition. Many results in determining the partition dimension of graphs have been obtained. However, the known results are limited to connected graphs. In this study, the notion of the partition dimension of a graph is extended so that it can be applied to disconnected graphs as well. Some lower and upper bounds for the partition dimension of a disconnected graph are determined (if they are finite). In this paper, also the partition dimensions for some classes of disconnected graphs are given.

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]

The partition dimension problem is to decompose the vertex set of a graph into minimum number of vertex disjoint sets such that the ordered distances between every vertex of the graph and the disjoint sets of that decomposition have different values in the representation. This problem has emerging applications in areas such as structure-activity issues in drug design, navigation of robots, pattern recognition and image processing. In the present study, we provide an upper bound for the partition dimension of parallel composition of any graphs and derive an exact result for parallel composition of paths with different lengths. On the other side, we find the partition dimension of the series composition of cycles and complete graphs with different sizes and an upper bound is derived for series composition of any graphs. Further, this problem is applied to a graph which has been generated by parallel and series composition together on paths. [ABSTRACT FROM AUTHOR]

An ordered k -partition Π = { S 1 , S 2 , ... , S k } of V (G) is called a resolving partition if for every two distinct vertices u , v ∈ V (G) , there exists a set S i in Π such that the distance between u and S i is not equal to the distance between v and S i. The minimum k for which there is a resolving k -partition of V (G) is called the partition dimension of G. In this paper, we provide the tight bounds for the partition dimension of rooted product graphs. Further, partition dimension of particular class of rooted product graphs has been studied. [ABSTRACT FROM AUTHOR]

Given a connected graph, the distancebetween two verticesis the length of a shortestu−vpath in G. The distancebetween a vertexand a subsetis defined as. An ordered partitionof vertices ofGis a resolving partition ofG, if for any two different verticesu,vofGthere existssuch that. The partition dimension ofGis the minimum number of sets in any resolving partition of G. In this article, we study the partition dimension of the lexicographic product of two graphs. [ABSTRACT FROM AUTHOR]

For a graph G = (V,E), a partition Ω ={O1,O2,...,Ok} of the vertex set V is called a resolving partition if every pair of vertices u,v ∊ V(G) have distinct representations under Ω. The partition dimension of G is the minimum integer k such that G has a resolving k-partition. Many results in determining the partition dimension of graphs have been obtained. However, the known results are limited to connected graphs. In this study, the notion of the partition dimension of a graph is extended so that it can be applied to disconnected graphs as well. Some lower and upper bounds for the partition dimension of a disconnected graph are determined (if they are finite). In this paper, also the partition dimensions for some classes of disconnected graphs are given. [ABSTRACT FROM AUTHOR]

Abstract: Let be a connected graph. The distance between two vertices , denoted by , is the length of a shortest -path in . The distance between a vertex and a subset is defined as , and it is denoted by . An ordered partition of vertices of a graph , is a resolving partition of , if all the distance vectors are different. The partition dimension of is the minimum number of sets in any resolving partition of . In this article we study the partition dimension of strong product graphs and Cartesian product graphs. Specifically, we prove that the partition dimension of the strong product of graphs is bounded below by four and above by the product of the partition dimensions of the factor graphs. Also, we give the exact value of the partition dimension of strong product graphs when one factor is a complete graph and the other one is a path or a cycle. For the case of Cartesian product graphs, we show that its partition dimension is less than or equal to the sum of the partition dimensions of the factor graphs minus one. Moreover, we obtain an upper bound on the partition dimension of Cartesian product graphs, when one factor is a complete graph. [Copyright &y& Elsevier]

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]

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]

Aims and Objective: The idea of partition and resolving sets play an important role in various areas of engineering, chemistry and computer science such as robot navigation, facility location, pharmaceutical chemistry, combinatorial optimization, networking, and mastermind game., Methods: In a graph, to obtain the exact location of a required vertex, which is unique from all the vertices, several vertices are selected; this is called resolving set, and its generalization is called resolving partition, where selected vertices are in the form of subsets. A minimum number of partitions of the vertices into sets is called partition dimension., Results: It was proved that determining the partition dimension of a graph is a nondeterministic polynomial time (NP) problem. In this article, we find the partition dimension of convex polytopes and provide their bounds., Conclusion: The major contribution of this article is that due to the complexity of computing the exact partition dimension, we provide the bounds and show that all the graphs discussed in the results have partition dimensions either less or equals to 4, but not greater than 4., (Copyright© Bentham Science Publishers; For any queries, please email at epub@benthamscience.net.)