A Finite Complete Set of Equations Generating Graphs

摘要

It was known that every graph can be constructed from a finite list of elementary graphs using the operations of graph sum and graph composition. We determine a complete set of "equations" or rewriting rules with the property that two expressions represent the same graph if and only if one can be transformed into the other by means of these rules.