Paper ID: 2459

On The Partition Dimension of Disconnected Graphs

Debi Oktia Haryeni, Edy Tri Baskoro & Suhadi Wido Saputro
Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung 40132, Indonesia.

Received: May 20th, 2016, 1st Revision: September 5th, 2016, Accepted to Publish: September 16th, 2016.

Abstract. For a graph G = (V;E); a partition Ω = {O1,O2,...,Ok} of V(G) of the vertex set V is called a resolving partition if every pair of vertices u,v ϵ V(G) have distinct representations under Ω: The partition dimension of G is the minimum integer k such that G has a resolving k-partition. Many results in determining the partition dimension of graphs have been obtained. However, known results are only limited for connected graphs. In this paper, we extend the notion of the partition dimension of a graph so that we could apply it to disconnected graphs as well. We determine some lower and upper bounds for the partition dimension of a disconnected graph (if they are finite). We also give the partition dimensions for some classes of disconnected graphs.

Keywords : resolving partition; partition dimension; disconnected graph.

Baskoro, E. T. & Darmaji, Further Results on Partition Dimension of Corona Products, AIP Conf. Proc., 1450, pp. 77-81, 2012.

Baskoro, E. T. & Darmaji, The Partition Dimension of Corona Product of Two Graphs, Far East J. Math. Sci., 66, pp. 181-196, 2012.

Chartrand, G., Salehi, E. & Zhang, P., On the Partition Dimension of A Graph, Congr. Numer., 130, pp. 157-168, 1998.

Chartrand, G., Salehi, E. & Zhang, P., The Partition Dimension of A Graph, Aequationes Math., 59, pp. 45-54, 2000.

Darmaji, Baskoro, E. T., Utunggadewa, S. & Simanjuntak, R., The Partition Dimension of Complete Multipartite Graph, a Special Caterpillar and a Windmill, J. Combin. Math. Combin. Comput., 71, pp. 209-215, 2009.

Fehr, M., Gosselin, S. & Oellermann, O., The Partition Dimension of Cayley Digraphs, Aequationes Math., 71, pp. 1-18, 2006.

Grigorious, C., Stephen, S., Rajan, B. & Miller, M., On Partition Dimension of a Class of Circulant Graphs, Inform. Process. Lett., 114, pp. 353-356, 2014.

Harary, F. & Melter, R. A., On the metric dimension of graph, Ars. Combin., 2, pp. 191-195, 1976.

Javaid, I. & Salman, M., Connected Resolving Partitions in Unicyclic Graphs, Appl. Math. Inf. Sci. Lett., 3, pp. 7-11, 2015.

Rodr´ıguesz-Vel´azquez, J. A., Yero, I. G. & Kuziak, D., The Partition Dimension of Corona Product Graphs, Preprint.

Rodr´ıguesz-Vel´azquez, J. A., Yero, I. G. & Lema´nska, M., On The Partition Dimension of Trees, Discrete Appl. Math., 166, pp. 204-209, 2014.

Slater, P. J., Leaves of trees, Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Congr. Numer., 14, pp. 549-559, 1975.

Tomescu, I., Discrepancies between metric dimension and partition dimension of a connected graph, Discrete Math., 308, pp. 5026-5031, 2008.

Tomescu, I., Javaid, I. & Slamin, On the Partition Dimension and Connected Partition Dimension of Wheels, Ars. Combinatoria, 84, pp. 311-317, 2007.

Yero, I. G., Kuziak, D. & Rodr´ıguesz-Vel´azquez, J.A., A note on the Partition Dimension of Cartesian Product Graphs, Appl. Math. Comput., 217, pp. 3571-3574, 2010.

Yero, I. G., Jakovac, M., Kuziak, D. & Taranenko, A., The Partition Dimension of Strong Product Graphs and Cartesian Product Graphs, Discrete Math., 331, pp. 43-52, 2014.

View my Stats

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.