格图和环面蜂巢图的角色分配问题

Everett和Borgatti引入了k 角色分配的概念。对于图G,它的一个k 角色分配就是由各顶点映到正整数 1,2,…k的一个函数,它满足:如果x和y有相同角色,那么分配到它们邻接点的角色的集合也相同。这种思想源自社会网络理论:我们说如果两个个体社会角色相同,那么和他们相联系的个体的总体社会角色类别相同。Lisheng等人在《三角化图的 2 角色分配》这篇文章中刻画了一类 2 角色可分配的图:无差图。并在开放问题中提出:k≥3时,能否找出k 角色可分配的图类和相应的分配方法? 笔者对格图和环面蜂巢图作了相应的研究。