On the star partition dimension of comb product of cycle and path

摘要

Let G= (V,E) be a connected graphs with vertex set V(G), edge set E(G) and S ? V(G). Given an ordered partition II= {S_1,S_2,S_3,...,S_k} of the vertex set V of G, the representation of a vertex v ∈ V with respect to II is the vector r(v|II)= (d(v,S _l),d(v,S_2),...,d(v,S_k)), where d(v,S_k) represents the distance between the vertex v and the set S_k and d(v,S_k)= min{d(v.x)|x ∈ S_k}. A partition II of V(G) is a resolving partition if different vertices of G have distinct representations, i.e., for every pair of vertices u, v e V(G), r(u|II) + r(v|II). The minimum k of II resolving partition is a partition dimension of G, denoted by pd(G). The resolving partition II= {S1,S2,S_3,...,S_k} is called a star resolving partition for G if it is a resolving partition and each subgraph induced by Si, 1 ≤ i ≤ k, is a star. The minimum k for which there exists a star resolving partition of V(G) is the star partition dimension of G, denoted by spd(G). Finding the star partition dimension of G is classified to be a NP-Hard problem. In this paper, we will show that the partition dimension of comb product of cycle and path namely C_(m ?) Pn and Pn ? C_m for n≥ 2 and m≥ 3.