A k-role assignment of graph is an assignment of role, if G is a graph, a k-role assignment is a surjective function mapping each vertex into apositive integer 1,2......k, so that if x and y have the same role, then thesets of roles assigned to their neighbors are the same. This idea motivated in social network theory, where one tries to define social roles so that if two individuals get the same social role, they associate with people of the same sets of role.In this paper, we discusses the k-role assignment for a special kind of graph, including path, circle, broad star-shaped tree, flower graph, and we provide algorithms to give role assignment for star-shaped graph and flower graphs. A k ?thershold close role assignment is a function mapping each vertex into a role, a opsitive integer 1,2, ...k, so that if x and y have the same role, then the Hausdorff distance of N(x) and N(y) is not more than 1. That is to say: r(x) = r(y# dh(r(N(x)),r(N(y)))≤ 1, On the base of Robert and Li Sheng, I have a deeper research. I define a notion d(G) of graph, then carry another research for the graphs with no isolated vertices.
|