Caracterização de 2-atribuição de papéis em produto corona de dois grafos

• Jarlilson Guajajara UFG
• Julliano Rosa Nascimento UFG

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

Resumo

O produto corona de G e H é o grafo G ◦ H obtido tomando uma cópia de G, |V (G)| cópias de H , e tornando o i-ésimo vértice de G adjacente a cada vértice da i-ésima cópia de H , onde 1 ≤ i ≤ |V (G)|. Uma r-atribuição é uma função dos vértices de G para um conjunto de papéis de tamanho r tal que, para quaisquer vértices mapeados para o mesmo papel, suas vizinhanças têm a mesma imagem. Neste artigo, apresentamos a caracterização da 2-atribuição de papéis para o produto corona de dois grafos, considerando todos os grafos de papéis possíveis com dois vértices.

Referências

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

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

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

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

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

Pekeč, A. e Roberts, F. S. (2001). The role assignment model nearly fits most social networks. Mathematical Social Sciences, 41(3):275–293.

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.

Sharma, R., Adhikari, B., e Krueger, T. (2019). Self-organized corona graphs: A deterministic complex network model with hierarchical structure. Advances in Complex Systems, 22(06):1950019.