Role Assignments in some Circulant Graphs

An r-role assignment of a simple graph G is an assignment of r distinct roles to the vertices of G, such that two vertices with the same role have the same set of roles assigned to related vertices. Furthermore, a specific r-role assignment defines a role graph, in which the vertices are the distinct r roles, and there is an edge between two roles whenever there are two adjacent vertices in the graph G that correspond to these roles. This study focuses on circulant graphs, which are undirected graphs with cyclic symmetry with edges determined by a set of distances. We show necessary and sufficient conditions for the existence of r-role assignments in all circulant graphs of the form C_n(1), for every fixed r ≥ 2.