Graph Operations and Free Graph Algebras

We introduce a concept of graph algebra that generalizes the traditional concept of algebra in the sense that (1) we use graphs rather than sets as carriers, and (2) we generalize algebraic operations to diagrammatic operations over graphs, which we call graph operations.Our main objective is to extend the construction of term algebras, i.e., free algebras, for the new setting. The key mechanism for the construction of free graph algebras are pushout-based graph transformations for non-deleting injective rules. The application of rules, however, has to be controlled in such a way that “no confusion” arises. For this, we introduce graph terms and present a concrete construction of free graph algebras as graph term algebras.As the main result of the paper, we obtain for any graph signature Γ$$\varGamma $$ an adjunction between the category Graph$$\mathsf {Graph}$$ of graphs and the category GAlg(Γ)$$\mathsf {GAlg}{(\varGamma )}$$ of graph Γ$$\varGamma $$-algebras. In such a way, we establish an “integrating link” between the two areas Hartmut Ehrig contributed most: algebraic specifications with initial/free semantics and pushout-based graph transformations.