The partition dimension of subdivision of a graph

• Main Authors: Amrullah, Baskoro, Edy Tri, Uttunggadewa, Saladin, Simanjuntak, Rinovia
• Format: Conference Proceeding
• Language: English
• Subjects: Lower bounds; Partitions
• ISSN: 0094-243X; 1551-7616
• DOI: 10.1063/1.4940802

Let G = (V,E) be a connected graph, u,v ∈ V (G), e = uv ∈ E(G) and k be a positive integer. A k−subdivision of an edge e is a replacement of e = uv with a path u, x 1, x 2, x ···, x k , v. A graph G with a k−subdivided edge is denoted with S(G(e; k)). Let p be a positive integer and Π = {L 1, L 2, L 3, …, Lp } be a p-partition of V (G). The representation of a vertex v with respect to Π, r(v|Π), is the vector (d(v, L 1), d(v, L 2), d(v, L 3),…, d(v, Lp )) where d(v, Li ) for i ∈ [1, p] is the minimum distance between v and the vertices of Li . The partition Π is called a resolving partition of G if r(w|Π) ≠ r(v|Π) for all w ≠ v ∈ V (G). The partition dimension, pd(G), of G is the smallest integer p such that G has a resolving p-partition. In this paper, we present sharp upper and lower bounds of the partition dimension of S(G(e; k)) for any graph G.