## Abstract

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 (GH) = {(a, u)|a ∈ V (G), u ∈ V (H)} and (a, u)(b, v) ∈ E(GH) 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.

Original language | English |
---|---|

Article number | 012005 |

Journal | Journal of Physics: Conference Series |

Volume | 855 |

Issue number | 1 |

DOIs | |

Publication status | Published - 12 Jun 2017 |

Event | 1st International Conference on Mathematics: Education, Theory, and Application, ICMETA 2016 - Surakarta, Indonesia Duration: 6 Dec 2016 → 7 Dec 2016 |

## Keywords

- Star resolving partition
- comb product
- complete graph
- cycle
- star partition dimension