On The Partition Dimension of Cm + Pn Graph

[摘要] 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.

[发布机构] 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