O produto forte de um grafo não trivial e o grafo completo possui 2- e 3-atribuição de papéis
Resumo
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 Kn, n ≥ 2, do qual concluímos que o produto forte entre G e Kn sempre possui 2- e 3-atribuição de papéis.
Referências
J. A. Bondy and U. S. R. Murty. Graph theory with applications, volume 290. Citeseer, New York, USA, 1976.
D. Castonguay, E. S. Dias, and F. N. Mesquita. Prismas complementares com 2-atribuição de papéis. Matematica Contemporânea, 46:83–93, 2018.
D. Castonguay, E. S. Dias, F. N. Mesquita, and J. R. Nascimento. Computing some role assignments of cartesian product of graphs. RAIRO-Oper. Res., 56(1):115–121, 2022.
D. Castonguay, E. S. Dias, F. N. Mesquita, and J. R. Nascimento. Computing role assignments of cartesian product of graphs. RAIRO-Oper. Res., 57(3):1075–1086, 2023.
R. Diestel. Graph theory. New York, USA, Springer-Verlag, 2000.
M. C. Dourado. Computing role assignments of split graphs. Theoretical Computer Science, 635:74–84, 2016.
M. G. Everett and S. Borgatti. Role colouring a graph. Mathematical Social Sciences, 21(2):183–188, 1991.
J. Fiala and D. Paulusma. A complete complexity classification of the role assignment problem. Theoretical computer science, 349(1):67–81, 2005.
R. H. Hammack, W. Imrich, and S. Klavžar. Handbook of product graphs, volume 2. CRC press Boca Raton, 2011.
T. R. Jensen and B. Toft. Graph coloring problems. John Wiley & Sons, 2011.
S. Lyle. Homomorphisms of graphs. PhD thesis, Clemson University, Clemson, South Carolina, 2008.
F. N. Mesquita. Atribuição de papéis em alguns produtos de grafos. PhD thesis, Universidade Federal de Goiás, 2022.
S. Pandey. Role colouring hereditary classes of graphs. PhD thesis, Indian Institute of Science Education and Research Pune, 2019.
C. Purcell and P. Rombach. On the complexity of role colouring planar graphs, trees and cographs. Journal of Discrete Algorithms, 35:1–8, 2015.
C. Purcell and P. Rombach. Role colouring graphs in hereditary classes. Theoretical Computer Science, 876:12–24, 2021.
F. S. Roberts and L. Sheng. How hard is it to determine if a graph has a 2-role assignment? Networks, 37(2):67–73, 2001.
P. van 't Hof, D. Paulusma, and J. M. van Rooij. Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40):3601–3613, 2010.
Y.-q. Zhao, W.-l. Feng, H. Li, and J.-m. Yang. k-role assignments under some graph operations. Journal of Hebei University of Science and Technology, page 06, 2010.
D. Castonguay, E. S. Dias, and F. N. Mesquita. Prismas complementares com 2-atribuição de papéis. Matematica Contemporânea, 46:83–93, 2018.
D. Castonguay, E. S. Dias, F. N. Mesquita, and J. R. Nascimento. Computing some role assignments of cartesian product of graphs. RAIRO-Oper. Res., 56(1):115–121, 2022.
D. Castonguay, E. S. Dias, F. N. Mesquita, and J. R. Nascimento. Computing role assignments of cartesian product of graphs. RAIRO-Oper. Res., 57(3):1075–1086, 2023.
R. Diestel. Graph theory. New York, USA, Springer-Verlag, 2000.
M. C. Dourado. Computing role assignments of split graphs. Theoretical Computer Science, 635:74–84, 2016.
M. G. Everett and S. Borgatti. Role colouring a graph. Mathematical Social Sciences, 21(2):183–188, 1991.
J. Fiala and D. Paulusma. A complete complexity classification of the role assignment problem. Theoretical computer science, 349(1):67–81, 2005.
R. H. Hammack, W. Imrich, and S. Klavžar. Handbook of product graphs, volume 2. CRC press Boca Raton, 2011.
T. R. Jensen and B. Toft. Graph coloring problems. John Wiley & Sons, 2011.
S. Lyle. Homomorphisms of graphs. PhD thesis, Clemson University, Clemson, South Carolina, 2008.
F. N. Mesquita. Atribuição de papéis em alguns produtos de grafos. PhD thesis, Universidade Federal de Goiás, 2022.
S. Pandey. Role colouring hereditary classes of graphs. PhD thesis, Indian Institute of Science Education and Research Pune, 2019.
C. Purcell and P. Rombach. On the complexity of role colouring planar graphs, trees and cographs. Journal of Discrete Algorithms, 35:1–8, 2015.
C. Purcell and P. Rombach. Role colouring graphs in hereditary classes. Theoretical Computer Science, 876:12–24, 2021.
F. S. Roberts and L. Sheng. How hard is it to determine if a graph has a 2-role assignment? Networks, 37(2):67–73, 2001.
P. van 't Hof, D. Paulusma, and J. M. van Rooij. Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40):3601–3613, 2010.
Y.-q. Zhao, W.-l. Feng, H. Li, and J.-m. Yang. k-role assignments under some graph operations. Journal of Hebei University of Science and Technology, page 06, 2010.
Publicado
07/12/2023
Como Citar
MEDEIROS, Gustavo Morais; NASCIMENTO, Julliano Rosa.
O produto forte de um grafo não trivial e o grafo completo possui 2- e 3-atribuição de papéis. In: ESCOLA REGIONAL DE INFORMÁTICA DE GOIÁS (ERI-GO), 11. , 2023, Goiânia/GO.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
DOI: https://doi.org/10.5753/erigo.2023.237360.
