Um estudo sobre atribuição de papéis em produto forte de grafos usando identificação de vértices gêmeos

• Gustavo Morais Medeiros UFG
• Julliano Rosa Nascimento UFG

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

Resumo

Seja G um grafo simples e r um inteiro positivo. Uma r-atribuição de papéis é uma atribuição de r papéis distintos aos vértices de G, tal que, dois vértices com o mesmo papel têm o mesmo conjunto de papéis nos vértices adjacentes. Dizemos que a atribuição de papéis é uma R-atribuição de papéis de G, quando R é um grafo e r = |V(R)|. Determinar se um grafo possui uma r-atribuição de papéis é NP-completo para r ≥ 3 fixo, mesmo restrito a grafos bipartidos ou cordais. Neste trabalho, investigamos a existência de atribuições de papéis no produto forte de grafos, explorando em particular como propriedades dos fatores - como a presença de vértices gêmeos em suas atribuições de papéis - influenciam as atribuições possíveis no produto.

Referências

Bondy, J. A. and Murty, U. S. R. (2008). Graph theory. Springer Publishing Company, Incorporated.

Castonguay, D., Dias, E. S., Mesquita, F. N., and Nascimento, J. R. (2022). Computing some role assignments of cartesian product of graphs. RAIRO-Oper. Res., 56(1):115–121.

Castonguay, D., Dias, E. S., Mesquita, F. N., and Nascimento, J. R. (2023). Computing role assignments of cartesian product of graphs. RAIRO-Oper. Res., 57(3):1075–1086.

Diestel, R. (2000). Graph theory. New York, USA, Springer-Verlag.

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

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

Hammack, R. H., Imrich, W., and Klavžar, S. (2011). Handbook of product graphs, volume 2. CRC press Boca Raton.

Medeiros, G. and Nascimento, J. (2024). 3-atribuição de papéis em produto forte de grafos bipartidos e grafos cordais sem folhas. In Anais do IX Encontro de Teoria da Computação, pages 90–94, Porto Alegre, RS, Brasil. SBC.

Medeiros, G. M. and Nascimento, J. R. (2023). O produto forte de um grafo não trivial e o grafo completo possui 2-e 3-atribuição de papéis. In Anais da XI Escola Regional de Informática de Goiás. SBC.

Pandey, S. (2019). Role colouring hereditary classes of graphs. PhD thesis, Indian Institute of Science Education and Research Pune.

van ’t Hof, P., Paulusma, D., and van Rooij, J. M. (2010). Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40):3601–3613.

Zhao, Y.-q., Feng, W.-l., Li, H., and Yang, J.-m. (2010). k-role assignments under some graph operations. Journal of Hebei University of Science and Technology, page 06.