On The Partition Dimension Of Caveman Graph, Gneralized Petersen, And Km *2Kn graph
Ilafiani Meta · 2017
ON THE PARTITION DIMENSION OF CAVEMAN GRAPH,GENERALIZED PETERSEN GRAPH, ANDKm∗2KnGRAPHMeta Ila ani, Tri Atmojo KusmayadiDepartment of MathematicsFaculty of Mathematics and Natural SciencesSebelas Maret UniversityAbstract.LetGbe a connected graph with vertex setV(G) ={v1;v2;:::;vn}andedge setE(G) ={e1;e2;:::;en}. Those vertices are divided intok-partition, denoted byS1;S2;:::;Sk. Let ={S1;S2;:::;Sk}be an orderedk-partition. The representationfor every vertexV(G) of is a minimum distance of a vertex to other vertices, denotedbyr(v|) = (d(v;S1);d(v;S2);:::;d(v;Sk)). If every vertex has distinct representation, is called a resolvingk-partition. Minimum cardinality ofk-partition ofV(G) is calledby partition dimension ofG, denoted bypd(G). In this research, we determine partitiondimension of caveman graphC(n;k), generalized Petersen graphP(n;k), andKm∗2Kngraph.Keywords: Partition dimension, caveman graph, generalized Petersen graph,Km∗2Kngraph.1.IntroductionThere are many concepts in graph discussed by researchers. One of thoseconcepts is partition dimension. This concept is introduced by Chartrand et al. [4]in 1998. Partition dimension ofGorpd(G) is minimum cardinality of a resolvingk-partition ofV(G).The concept of partition dimension has been applied frequently in some graphclasses. In 1998, Chartrand et al. [4] studied about partition dimension of pathgraph, complete graph, and cycle graph. Then, Asmiati [2] found partition dimensionof amalgamation of stars graph in 2012. Thereafter, in 2016, Apriliani [1] determinedpartition dimension of antiprism graph, mongolian tent graph, and stacked bookgraph. Also in 2016, Dewi [5] determined partition dimension of some graph classes,such as lollipop graph, generalized Jahangir graph, andCn∗2Kmgraph. In thisresearch, we determine partition dimension of caveman graphC(n; k) forn; k≥3,generalized Petersen graphP(n; k) forn≥5; k= 2 andn≥8; k= 3, andKm∗2Kngraph form; n≥3.