Author: Herman Servatius,
Reference: Journal of Algebra, 126, (1), pp. 34--60, 1989.
A graph group is a finitely generated group whose only relations are that certain of the generators are allowed to commute with one another. Such a group may be used to model a finite set of reversible processes, with those processes that may be run in parallel corresponding to generators which commute.
A graph group may be described by the graph G whose vertices are the generators with commuting generators joined by an edge, and the graph is denoted by F(G).
In this article the word, conjugacy and centralizer problems are solved, with the solutions of each leading to polynomial time algorithms.
As an application, it is shown that, for some graph groups, Aut(F(G))
is finitely generated by generators which are natural analogues to the
Neilsen automorphisms for a free group.