Graphs with <i>k</i>-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.