O produto forte de um grafo não trivial e o grafo completo possui 2- e 3-atribuição de papéis - Medeiros, Gustavo Morais; Nascimento, Julliano Rosa (Anais da Escola Regional de Informática de Goiás (ERI-GO); 2023: Anais da XI Escola Regional de Informática de GoiásDO - 10.5753/erigo.2023.237360, 2023)
Seja G um grafo simples e r um inteiro positivo. Com aplicações em análise de redes sociais, 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. Sabe-se que o problema de decidir se um grafo arbitrário G possui uma r-atribuição é NP-completo para r ≥ 2, e há poucos resultados na literatura sobre esse problema para produtos de grafos. Nesse aspecto, apresentamos um algoritmo linear para determinar 2- e 3-atribuição de papéis para o produto forte entre um grafo não trivial G e K n , n ≥ 2, do qual concluímos que o produto forte entre G e K n sempre possui 2- e 3-atribuição de papéis.