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

has been cited by the following article:

• TITLE: Graphs with k-Role Assignments

  AUTHORS: Yana Liu, Yongqiang Zhao

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

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.7 No.3, July 20, 2017

  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.