The strong product of a non-trivial graph and the complete graph and has 2- and 3-role assingment

• Gustavo Morais Medeiros UFG
• Julliano Rosa Nascimento UFG

DOI: https://doi.org/10.5753/erigo.2023.237360

Abstract

Let G be a simple graph and r a positive integer. With applications in social network analysis, an r-role assignment is an assignment of r distinct roles to the vertices of G, such that two vertices with the same role share the same set of roles among their adjacent vertices. It is known that the problem of deciding whether an arbitrary graph G has an r-role assignment is NP-complete for r ≥ 2, and there are few results in the literature on this problem for graph products. In this regard, we present a linear-time algorithm to determine 2- and 3-role assignments for the strong product of a nontrivial graph G and K_n, n ≥ 2, which we conclude that the strong product of G and K_n always has 2- and 3-role assignments.

References

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.