The Hopf Algebra of graph invariants

Understand

We propose an algebraic study of the simple graph isomorphism problem.

• We define a Hopf algebra from an explicit realization of its elements as formal power series.
• We show that these series can be evaluated on graphs and count occurrences of subgraphs.
• We establish a criterion for the isomorphism test of two simple graphs by means of occurrence counting of subgraphs.