On the Partition Dimension and the Twin Number of a Graph

Carmen Hernando, Merce mora, Ignacio M Pelayo

Published 2016-02-29Version 1

A partition P of the vertex set of a connected graph G is a locating partition of G if every vertex is uniquely determined by its vector of distances to the elements of P. The partition dimension of G is the minimum cardinality of a locating partition of G. A pair of vertices u,v of a graph G are called twins if they have exactly the same set of neighbors other than u and v. A twin class is a maximal set of pairwise twin vertices. The twin number of a graph G is the maximum cardinality of a twin class of G. In this paper we undertake the study of the partition dimension of a graph by also considering its twin number. This approach allows us to obtain the set of connected graphs of order n having partition dimension n-2. This set is formed by exactly 15 graphs, instead of 23, as was wrongly stated in the paper: "Discrepancies between metric dimension and partition dimension of a connected graph", published in Discrete Mathematics in 2008.