Name
Abstract | ||
|---|---|---|
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 G 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. (C) 2001 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1002/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9 | NETWORKS |
Keywords | Field | DocType |
social networks,social role,role assignment,role coloring,NP-completeness | Combinatorics,Forbidden graph characterization,Graph power,Graph factorization,Graph labeling,Regular graph,Null graph,Mathematics,Voltage graph,Complement graph | Journal |
Volume | Issue | ISSN |
37 | 2 | 0028-3045 |
Citations | PageRank | References |
15 | 1.85 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fred S. Roberts | 1 | 527 | 85.71 |
| Li Sheng | 2 | 20 | 4.67 |