Um estudo sobre atribuição de papéis em produto forte de grafos usando identificação de vértices gêmeos - Medeiros, Gustavo Morais; Nascimento, Julliano Rosa (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2025.9021, 2025)
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.