OJDM  Vol.7 No.3 , July 2017
Graphs with k-Role Assignments
Abstract: 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.
Cite this paper: Liu, Y. and Zhao, Y. (2017) Graphs with k-Role Assignments. Open Journal of Discrete Mathematics, 7, 177-184. doi: 10.4236/ojdm.2017.73016.

[1]   Everett, M.G. and Borgatti, S. (1991) Role Colouring a Graph. Mathematical Social Sciences, 21, 183-188.

[2]   Pekec, A. and Roberts, F.S. (2001) The Role Assignment Model Nearly Fits Most Social Networks. Mathematical Social Sciences, 41, 275-293.

[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.

[8]   Dourado, M.C. (2016) Computing Role Assignments of Split Graphs. Theoretical Computer Science, 635, 74-84.

[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.<67::AID-NET1>3.0.CO;2-9

[10]   Sheng, L. (2003) 2-Role Assignments on Triangulated Graphs. Theoretical Computer Science, 304, 201-214.

[11]   Roberts, F.S. and Sheng, L. (1997) Threshold Role Assignments. Congressus Numerantium, 123, 135-148.