On the star partition dimension of comb product of cycle and complete graph

Ridho Alfarisi*, Darmaji, Dafik

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

11 Citations (Scopus)


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 Π = {S1, S2, S3, ⋯, Sk } of V (G), the representation of a vertex v ∈ V (G) with respect to Π is the k-vectors r(v|Π) = (d(v, S1), d(v, S2), ⋯, d(v, Sk )), where d(v, Sk ) represents the distance between the vertex v and the set Sk , defined by d(v, Sk ) = min{d(v, x)|x ∈ Sk}. 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 Π = {S1, S2, S3, ⋯, Sk} 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 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 CnKm and KmCn for n ≥ 3 and m ≥ 3.

Original languageEnglish
Article number012005
JournalJournal of Physics: Conference Series
Issue number1
Publication statusPublished - 12 Jun 2017
Event1st International Conference on Mathematics: Education, Theory, and Application, ICMETA 2016 - Surakarta, Indonesia
Duration: 6 Dec 20167 Dec 2016


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


Dive into the research topics of 'On the star partition dimension of comb product of cycle and complete graph'. Together they form a unique fingerprint.

Cite this