TY - GEN
T1 - On the partition dimension of comb product of path and complete graph
AU - Darmaji,
AU - Alfarisi, Ridho
N1 - Publisher Copyright:
© 2017 Author(s).
PY - 2017/8/1
Y1 - 2017/8/1
N2 - For a vertex v of a connected graph G(V, E) 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). Finding the 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 path and complete graph. The results show that comb product of complete grapph Km and path Pn namely pd(Km>Pn)=m where m ≥ 3 and n ≥ 2 and pd(Pn>Km)=m where m ≥ 3, n ≥ 2 and m ≥ n.
AB - For a vertex v of a connected graph G(V, E) 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). Finding the 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 path and complete graph. The results show that comb product of complete grapph Km and path Pn namely pd(Km>Pn)=m where m ≥ 3 and n ≥ 2 and pd(Pn>Km)=m where m ≥ 3, n ≥ 2 and m ≥ n.
KW - Resolving partition
KW - comb product
KW - complete graph
KW - partition dimension
KW - path
UR - http://www.scopus.com/inward/record.url?scp=85027972902&partnerID=8YFLogxK
U2 - 10.1063/1.4994441
DO - 10.1063/1.4994441
M3 - Conference contribution
AN - SCOPUS:85027972902
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 -