On The Partition Dimension of Cm + Pn Graph

International Conference on Mathematics: Education, Theory and Application

数学;教育

Vertana, Hidra^1 ; Kusmayadi, Tri Atmojo^1

Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Sebelas Maret, Surakarta, Indonesia^1

关键词: Cardinalities;    Connected graph;    Cycle graphs;    Join operation;    K-partition;    Partition dimensions;    Positive integers;    Resolving partitions;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/855/1/012058/pdf
DOI  :  10.1088/1742-6596/855/1/012058

学科分类：发展心理学和教育心理学

来源: IOP

【 摘 要 】

Let G be a connected graph with V (G) = {v1, v2, , vi} and E(G) = {e1, e2, , ej}, where V (G) is vertex set and E(G) is edge set. If S ⊆ V (G) and v ∈ V (G), then the distance between v and S is de ned by d(v, S) = min{d(v, x)|x ∈ S}. For an ordered k-partition Π = {S1, S2, , Sk} of V (G), the representation of v with respect to Π is r(v|Π) with r(v|Π) = (d(v, S1), d(v, S2), , d(v, Sk)). If the representation of v ∈ V (G) with respect to Π are distinct, so Π is called a resolving partition of V (G). The minimum cardinality of resolving partition Π is called a partition dimension of G, denoted by pd(G). In this paper, we study the partition dimension of a Cm+ Pngraph. Cm+ Pngraph is a graph formed from join operation of cycle graph Cmwith order m ≥ 3 and path Pnwith order n ≥ 2. Cm+ Pnis the union Cm∪ Pntogether with all edges uavb, for ua∈ V (Cm) and vb∈ V (Pn) with 1 ≤ a ≤ m and 1 ≤ b ≤ n. We obtain the partition dimension of Cm+ Pngraph is pd(C3+ Pn) = g where g is the smallest positive integer such that n ≤ 5g - 12 for g = 5 and n ≤ g3-7g2+20g-18/2 for g ≥ 6, and pd(Cq+ Pn) = min{p + f, r + t, x + y} for q ≥ 4 and n ≥ 2 where p, f, r, t, x and y are some positive integers related to the number of partition classes containing vertices of Cqand Pn.