In this paper we study the realizability question for commuting graphs of finite groups: Given an undirected graph $X$ is it the commuting graph of a group $G$? And if so, to determine such a group. We seek efficient algorithms for this problem. We make some general observations on this problem, and obtain a polynomial-time algorithm for the case of extraspecial groups.
翻译:在本文中,我们研究了有限组群通勤图的可变性问题:在未定向的图表中,X$是一组群的通勤图吗?如果是这样,我们为这一问题寻找有效的算法。我们对这个问题做了一些一般性观察,为特殊组群的情况获取了多元时算法。