On the partition dimension of directed circulant graphs

Abstract

The directed circulant graph C_n(1, 2, … , t) consists of the vertices v₀ , v₁ , … , v_n-1 and edges directed from v_i to v_i+j for every i = 0, 1, … , n – 1, and j = 1, 2, … , t, where 1 ≤ t ≤ n – 1, the indices are taken modulo n. We present lower and upper bounds on the partition dimension of very general graphs C_n(1, 2, … , t). Our bounds yield exact values of the partition dimension of the graphs C_n(1, 2, … , t) for t = 2, 3, 4 and n ≥ 10.

Subject Classification: (2010):

• 05C35
• 05C12

Keywords:

• Circulant graph
• Partition dimension
• Extremal graph theory
• Distance