On the star partition dimension of comb product of cycle and complete graph
Ridho Alfarisi, Darmaji, Dafik Dafik · Journal of Physics Conference Series · 2017
Let G = ( V, E ) be a connected graphs with vertex set V ( G ), edge set E ( G ) and S ⊆ V ( G ). For an ordered partition Π = { S 1 , S 2 , S 3 , …, S k } of V ( G ), the representation of a vertex v ∈ V ( G ) with respect to Π is the k -vectors r ( v |Π) = ( d ( v , S 1 ), 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 , defined by d ( v, S k ) = min { d ( v, x )| x ∈ S k } . The partition Π of V ( G ) is a resolving partition if the k -vektors r ( v| Π), v ∈ V ( G ) are distinct. The minimum resolving partition Π is a partition dimension of G , denoted by pd ( G ). The resolving partition Π = { S 1 , S 2 , S 3 , …, S k } is called a star resolving partition for G if it is a resolving partition and each subgraph induced by S i , 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 a star partition dimension of G is classified to be a NP-Hard problem. Furthermore, the comb product between G and H , denoted by G ⊲ H , is a graph obtained by taking one copy of G and |V ( G )| copies of H and grafting the i -th copy of H at the vertex o to the i -th vertex of G . By definition of comb product, we can say that V ( G ⊲ H ) = { ( a, u ) |a ∈ V ( G ), u ∈ V ( H ) } and ( a, u )( b, v ) ∈ E ( G ⊲ H ) whenever a = b and uv ∈ E ( H ), or ab ∈ E ( G ) and u = v = o . In this paper, we will study the star partition dimension of comb product of cycle and complete graph, namely C n ⊲ K m and K m ⊲ C n for n ≥ 3 and m ≥ 3.