Atribuição de papéis sob restrições núcleo–periferia em produto corona de grafos

• Jarlilson Guajajara UFG
• Diane Castonguay UFG
• Julliano Rosa Nascimento UFG

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

Resumo

Uma r-atribuição de papéis é uma função sobrejetora de V (G) em um conjunto de r papéis tal que quaisquer dois vértices com o mesmo papel têm o mesmo conjunto de papéis em suas vizinhanças. Neste artigo, estudamos como a estrutura núcleo-periferia do produto corona restringe atribuições de papéis. Também caracterizamos quando o grafo de papéis R_3,2, que não assume tal estrutura, pode ocorrer como grafo de papéis de um produto corona.

Referências

Borgatti, S. e Everett, M. (1999). Models of core/periphery structures. Social Networks, 21:375–395.

Castonguay, D., Dias, E. S., Mesquita, F. N., e Nascimento, J. R. (2025). Computing a 3-role assignment is polynomial-time solvable on complementary prisms. International Journal of Foundations of Computer Science, 0(0):1–24.

Dourado, M. C. (2016). Computing role assignments of split graphs. Theoretical Computer Science, 635:74–84.

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

Fiala, J. e Paulusma, D. (2005). A complete complexity classification of the role assignment problem. Theoretical Computer Science, 349(1):67–81.

Frucht, R. e Harary, F. (1970). On the corona of two graphs. Aequationes mathematicae, 4(3):322–325.

Guajajara, J. e Nascimento, J. (2024). Caracterização de 2-atribuição de papéis em produto corona de dois grafos. In Anais do IX Encontro de Teoria da Computação, pages 139–143, Porto Alegre, RS, Brasil. SBC.

Medeiros, G. M. e Nascimento, J. R. (2025). Sobre a 4-atribuição de papéis para produto forte de grafos. In Book of Abstracts of the LVII Brazilian Symposium on Operations Research, Gramado. Galoá. Anais eletrônicos.

Pandey, S. e Sahlot, V. (2022). Role coloring bipartite graphs. Discrete Applied Mathematics, 322:276–285.

Purcell, C. e Rombach, P. (2015). On the complexity of role colouring planar graphs, trees and cographs. Journal of Discrete Algorithms, 35:1–8.

Roberts, F. S. e Sheng, L. (2001). How hard is it to determine if a graph has a 2-role assignment? Networks, 37(2):67–73.

Rossi, R. A., Jin, D., Kim, S., Ahmed, N. K., Koutra, D., e Lee, J. B. (2020). On proximity and structural role-based embeddings in networks: Misconceptions, techniques, and applications. ACM Trans. Knowl. Discov. Data, 14(5).