The Research Of Several Open Problems On Role Assignments And Threshold Role Assignments

Everett and Borgatti introduced the concept: k-role assignment of graph .If G is a graph,a k-role assignment is a surjective function mapping each vertex into a positive integer 1,2......k, so that if x and y havethe same role,then the sets 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.Li Sheng and Roberts studied 2-role assignments on triangulated graphs.They puts the open questions:whether a given graph is k-role assignable for the case k ≥3 ? We study G_n^d,s graph and the grid graph and the honeycomb rectanglar torus and honeycomb rhombic torus accordingly.The graph with k-role assignment has many exquisite property,which results in the confined applicability ,so Roberts introduced the follow concept:k-thersholdclose role assignment of graph, Roberts and LiSheng showed that every graph of at least k vertice is k-threshhold close assignable for k=1,2,3,4,5. We prove in this paper that almost every graph is 7-threshhold close assignable and offer a impactful method to distinguish whether a graph is 7-threshhold close assignable which make the problem machine-readable. We resovle the problem in sense of probability,which has the significance that the method can be apply to more problem.