Article

The partition dimension of circulant graphs

Published in: Quaestiones Mathematicae
Volume 41, issue 1, 2018 , pages: 49–63
DOI: 10.2989/16073606.2017.1370031
Author(s): Elizabeth C.M. MaritzDepartment of Mathematics and Applied Mathematics, South Africa, Tomáš VetríkDepartment of Mathematics and Applied Mathematics, South Africa

Abstract

Let Π = {S1, S2, . . . , Sk} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex vV (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S1), d(v, S2), . . . , d(v, Sk)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, vV (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(Cn(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.

Get new issue alerts for Quaestiones Mathematicae