A study on role assignment in strong product of graphs using twin vertex identification

• Gustavo Morais Medeiros UFG
• Julliano Rosa Nascimento UFG

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

Abstract

Let G be a simple graph and r a positive integer. An r-role assignment is an assignment of r distinct roles to the vertices of G, such that two vertices with the same role have the same set of roles among their adjacent vertices. We say that a role assignment is an R-role assignment of G when R is a graph and r = |V(R)|. Determining whether a graph has an r-role assignment is NP-complete for fixed r ≥ 3, even when restricted to bipartite or chordal graphs. In this work, we investigate the existence of role assignments in the strong product of graphs, exploring in particular how properties of the factor graphs - such as the presence of twin vertices in their role assignments - influence the possible assignments in the product.

References

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.