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.