Graphs with k-Role Assignments

Yana  Liu; Yongqiang  Zhao

doi:10.4236/ojdm.2017.73016

Yana Liu, Yongqiang Zhao^*

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.

Keywords: Neighborhood, k-Role Assignment, Restricted Size k-Role Assignment, k-Threshold Close Role Assignment

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.

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.