p−Role Assignment for Cayley Graph Hℓ,p

• Athos J. de Araújo UFG https://orcid.org/0009-0006-1797-9309
• Paulo F. Candia IF Goiano https://orcid.org/0009-0009-2437-1782
• André da Cunha Ribeiro IF Goiano https://orcid.org/0000-0003-0641-854X

DOI: https://doi.org/10.5753/etc.2026.23602

Resumo

We study the role assignment problem in the family of Cayley graphs H_ℓ,p. We show that there exists a natural graph homomorphism from H_ℓ,p to a circulant graph Γ, which implies that every graph in this family admits a p-role assignment. We also present an efficient algorithm to compute such assignments in O(ℓp^ℓ−1) time. Our results highlight the interplay between algebraic structure and role assignments in highly symmetric graphs.

Referências

Everett, M. G. and Borgatti, S. (1991). Role colouring a graph. Mathematical Social Sciences, 21(2):183–188.

Holyer, I. (1981). The NP-Completeness of Some Edge-Partition Problems. SIAM Journal on Computing, 10(4):713–717.

Mesquita, F. (2022). Atribuição de papéis em alguns produtos de grafos. PhD thesis, PhD thesis, Universidade Federal de Goiás.

Ribeiro, A. C., de Figueiredo, C. M. H., and Kowada, L. A. B. (2010). An evidence for Lovász conjecture about Hamiltonian paths and cycles. Matemática Contemporânea, 39:128.

Ribeiro, A. C., Kowada, L. A. B., and de Figueiredo, C. M. H. (2014). Two families of cayley graph interconnection networks. Matemática Contemporânea, 42:105–114.