Premium
How hard is it to determine if a graph has a 2‐role assignment?
Author(s) -
Roberts Fred S.,
Sheng Li
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200103)37:2<67::aid-net1>3.0.co;2-9
Subject(s) - research center , library science , citation , computer science , center (category theory) , operations research , mathematics , political science , law , chemistry , crystallography
Role assignments, introduced by Everett and Borgatti [2], who called them role colorings, formalize the idea, arising in the theory of social networks, that individuals of the same social role will relate in the same way to the individuals playing counterpart roles. If is a graph, a k ‐role assignment is a function r mapping the vertex set onto the set of integers {1,2, … , k } so that if r ( x ) = r ( y ) then the sets of roles assigned to the neighbors of x and y are the same. We ask how hard it is to determine if a graph has a 2‐role assignment and show that recognizing if a graph has a 2‐role assignment is NP‐complete. © 2001 John Wiley & Sons, Inc.