On The Partition Dimension of Disconnected Graphs

Debi Oktia Haryeni, Edy Tri Baskoro, Suhadi Wido Saputro


For a graph G=(V,E), a partition Ω={O1,O2,…,Ok} of the vertex set V is called a resolving partition if every pair of vertices u,vV(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, the known results are limited to connected graphs. In this study, the notion of the partition dimension of a graph is extended so that it can be applied to disconnected graphs as well. Some lower and upper bounds for the partition dimension of a disconnected graph are determined (if they are finite). In this paper, also the partition dimensions for some classes of disconnected graphs are given.


disconnected graph; distance; forest; partition dimension; resolving partition

Full Text:



Chartrand, G., Salehi, E. & Zhang, P., On the Partition Dimension of a Graph, Congr. Numer., 131, pp. 55-66, 1998.

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

Harary, F. & Melter, R.A., On the Metric Dimension of Graph, Ars. Combin., 2, pp. 191-195, 1976.

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

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. Combin., 84, pp. 311-317, 2007.

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

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.

Rodríguez-Velázquez, J.A., Yero, I.G. & Lemanska M., On the Partition Dimension of Trees, Discrete Appl. Math., 166, pp. 204-209, 2014.

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.

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

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.

Rodríguez-Velázquez, J.A., Yero, I.G. & Kuziak, D., The Partition Dimension of Corona Product Graphs, Ars. Combin., To appear.

Yero, I.G., Kuziak, D. & Rodríguez-Velázquez, 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.

DOI: http://dx.doi.org/10.5614%2Fj.math.fund.sci.2017.1.2


  • There are currently no refbacks.

View my Stats

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