The Hopf Algebra of graph invariants

Abstract

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. This criterion is deduced from algebraic relations between elements of our algebra.

arXiv comment12 pages, submitted to FPSAC2016

References in corpus (2)

• Generating tuples of integers modulo the action of a permutation group and applications
• The Algebra of Graph Invariants - Lower and Upper Bounds for Minimal Generators