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

Ridho Alfarisi*, D. Darmaji

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)

Abstract

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 Π = {S1, S2, S3, ..., Sk} of the vertex set V of G, the representation of a vertex v ∈ V with respect to Π is the vector 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 and d(v, Sk) = min{d(v, x)|x ∈ Sk }. A partition Π of V(G) is a resolving partition if different vertices of G have distinct representations, i.e., for every pair of vertices u, v ∈ V(G), r(u|Π) ≠ r(v|Π). The minimum k of Π 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 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 Cm>Pn and Pn>Cm for n ≥ 2 and m ≥ 3.

Original languageEnglish
Title of host publicationInternational Conference on Mathematics - Pure, Applied and Computation
Subtitle of host publicationEmpowering Engineering using Mathematics
EditorsDieky Adzkiya
PublisherAmerican Institute of Physics Inc.
ISBN (Electronic)9780735415478
DOIs
Publication statusPublished - 1 Aug 2017
Event2nd International Conference on Mathematics - Pure, Applied and Computation: Empowering Engineering using Mathematics, ICoMPAC 2016 - Surabaya, Indonesia
Duration: 23 Nov 2016 → …

Publication series

NameAIP Conference Proceedings
Volume1867
ISSN (Print)0094-243X
ISSN (Electronic)1551-7616

Conference

Conference2nd International Conference on Mathematics - Pure, Applied and Computation: Empowering Engineering using Mathematics, ICoMPAC 2016
Country/TerritoryIndonesia
CitySurabaya
Period23/11/16 → …

Keywords

  • Star resolving partition
  • comb product
  • cycle
  • path
  • star partition dimension

Fingerprint

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

Cite this