The Partition Dimension of a Complete Multipartite Graph, a Special Caterpillar and a Windmill

Darmaji 1, S. Uttunggadewa1, R. Simanjuntak1, E.T. Baskoro1
1Combinatorial Mathematics Research Group Faculty of Mathematics and Natural Sciences Institut Teknologi Bandung (ITB) Jalan Ganesha No. 10 Bandung 40132, Indonesia.

Abstract

In this paper, we determine the partition dimension of a complete multipartite graph \( K_{n_1, n_2, \ldots, n_r} \), namely \( pd(K_{n_1, n_2, \ldots, n_r}) \). We show that \( pd(K_{n_1, n_2, \ldots, n_r}) = r + n – 1 \) if \( n_i = n \) for \( 1 \leq i \leq r \), and \( pd(K_{n_1, n_2, \ldots, n_r}) = r + n – 2 \) for \( n = n_1 \geq n_2 \geq \ldots \geq n_r \). We also show that the partition dimension of the caterpillar graph \( C_n^m \) is \( m \) for \( n \leq m \) and \( m + 1 \) for \( n > m \), and the partition dimension of the windmill graph \( W_{2}^{n} \) is \( k \), where \( k \) is the smallest integer such that \( \binom{k}{2} \geq m \).

Keywords: caterpillar, complete muitipartite graph, partition dimension, resolving partition, windmill graph.