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 -