TY - GEN

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

AU - Alfarisi, Ridho

AU - Darmaji, D.

N1 - Publisher Copyright:
© 2017 Author(s).

PY - 2017/8/1

Y1 - 2017/8/1

N2 - 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.

AB - 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.

KW - Star resolving partition

KW - comb product

KW - cycle

KW - path

KW - star partition dimension

UR - http://www.scopus.com/inward/record.url?scp=85028010815&partnerID=8YFLogxK

U2 - 10.1063/1.4994419

DO - 10.1063/1.4994419

M3 - Conference contribution

AN - SCOPUS:85028010815

T3 - AIP Conference Proceedings

BT - International Conference on Mathematics - Pure, Applied and Computation

A2 - Adzkiya, Dieky

PB - American Institute of Physics Inc.

T2 - 2nd International Conference on Mathematics - Pure, Applied and Computation: Empowering Engineering using Mathematics, ICoMPAC 2016

Y2 - 23 November 2016

ER -