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 -