Computing role assignments of split graphs

详细信息    查看全文

• 作者：Mitre Costa Dourado¹ ; ^{mitre@dcc.ufrj.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Algorithms ; NP-complete problems ; Role assignments ; Split graphs ; Social networks
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 July 2016
• 年：2016
• 卷：635
• 期：Complete
• 页码：74-84
• 全文大小：458 K

文摘

A k-role assignment of a simple graph G   is a surjective function r:V(G)→{1,…,k}$r:V(G)\to \{1,\dots ,k\}$ where {r(u^′):u^′∈N(u)}={r(v^′):v^′∈N(v)}$\{r(u^{\prime }):u^{\prime }\in N(u)\}=\{r(v^{\prime }):v^{\prime }\in N(v)\}$ for every pair facca729073c349f9d0c51ff9f0" title="Click to view the MathML source">u,v∈V(G)$u,v\in V(G)$ with r(u)=r(v)$r(u)=r(v)$. This concept appears in the context of social networks. It is known that the problem of finding a 2-role assignment of chordal graphs can be solved in linear time and that deciding whether a graph of this class admits a k  -role assignment, for any fixed k≥3$k\ge 3$, is NP-complete. In this work, we investigate this problem on split graphs, a subclass of chordal graphs. We characterize the split graphs admitting a 3-role assignment. Such result leads to a linear time algorithm for this case. Furthermore, we prove that deciding whether a split graph has a k-role assignment is NP-complete for any fixed k≥4$k\ge 4$.