For a given graph G, a k-role assignment of G is a surjective function ？such that , where N(x) and N(y) are the neighborhoods of x and y, respectively. Furthermore, as we limit the number of different roles in the neighborhood of an individual, we call r a restricted size k-role assignment. When the hausdorff distance between the sets of roles assigned to their neighbors is at most 1, we call r a k-threshold close role assignment. In this paper we study the graphs that have k-role assignments, restricted size k-role assignments and k-threshold close role assignments, respectively. By the end we discuss the maximal and minimal graphs which have k-role assignments.
References
[1]
Everett, M.G. and Borgatti, S. (1991) Role Colouring a Graph. Mathematical Social Sciences, 21, 183-188. https://doi.org/10.1016/0165-4896(91)90080-B
[2]
Pekec, A. and Roberts, F.S. (2001) The Role Assignment Model Nearly Fits Most Social Networks. Mathematical Social Sciences, 41, 275-293. https://doi.org/10.1016/S0165-4896(00)00064-0
[3]
Roberts, F.S. (1998) Role Assignments and Indifference Graphs. In: Dowing, C., Roberts, F.S. and Theuns, P., Eds., Recent Trends in Mathematical Psychology, Lawrence Erlbaum Associates, Mahwah, 33-46.
[4]
Roberts, F.S. and Sheng, L. (1996) Role Primitive Indifference Graphs and the Role Assignments on w-Fan Graphs. Congressus Numerantium, 121, 65-75.
[5]
Roberts, F.S. and Sheng, L. (1999) Role Assignments. In: Alavi, Y., Lick, D.R. and Schwenk, A., Eds., Combinatorics, Grsph Theory, and Algorithms, Vol. 2, New Issues Press, Kalamazoo, 729-745.
[6]
Van’t Hof, P., Paulusma, D. and Van Rooij, J.M.M. (2010) Computing Role Assignments of Chordal Graphs. Theoretical Computer Science, 411, 3601-3613.
[7]
Heggernes, P., Van’t Hof, P. and Paulusma, D. (2012) Computing Role Assignments of Proper Interval Graphs in Polynomial Time. Journal of Discrete Algorithms, 14, 173-188. https://doi.org/10.1016/j.jda.2011.12.004
[8]
Dourado, M.C. (2016) Computing Role Assignments of Split Graphs. Theoretical Computer Science, 635, 74-84. https://doi.org/10.1016/j.tcs.2016.05.011
[9]
Roberts, F.S. and Sheng, L. (2001) How Hard Is It to Determine if a Graph Has a 2-Role Assignment. Networks, 37, 67-73. https://doi.org/10.1002/1097-0037(200103)37:2<67::AID-NET1>3.0.CO;2-9
[10]
Sheng, L. (2003) 2-Role Assignments on Triangulated Graphs. Theoretical Computer Science, 304, 201-214. https://doi.org/10.1016/S0304-3975(03)00084-7
[11]
Roberts, F.S. and Sheng, L. (1997) Threshold Role Assignments. Congressus Numerantium, 123, 135-148.
![\"\"](\"Edit_d1cca999-a2af-4efc-bf5d-b38d2f1ad213.bmp\")
？such that ![\"\"](\"Edit_a4d37d51-d314-4211-95de-53a47c80e2fa.bmp\")
, where N(x) and N(y) are the neighborhoods of x and y, respectively. Furthermore, as we limit the number of different roles in the neighborhood of an individual, we call r a restricted size k-role assignment. When the hausdorff distance between the sets of roles assigned to their neighbors is at most 1, we call r a k-threshold close role assignment. In this paper we study the graphs that have k-role assignments, restricted size k-role assignments and k-threshold close role assignments, respectively. By the end we discuss the maximal and minimal graphs which have k-role assignments.
