Hopf algebra of graphs

Let $B$ be the set of isomorphism classes of finite graphs. Let $V$ be the $k$-vector space freely generated by $B$. I have heard that $V$ carries the structure of a Hopf algebra, and would like to understand the details.

The multiplication is defined by linear extension of the disjoint union of graphs. The unit is the empty graph. The comultiplication sends a graph $G$ to the sum $\sum_{S \subseteq V(G)} G|_S \otimes G|_{V(G) \setminus S}$, running over all subsets of vertices of $G$. The counit maps the empty graph to $1$, and all other graphs to $0$. I have checked that we get a commutative cocommutative bialgebra.

Question. How to define the antipode?

Although the antipode $S$ of a Hopf algebra is unique, I cannot come up with it. I am pretty sure that the antipode maps a graph to an alternating sum of graphs. Only then $V \to V \otimes V \xrightarrow{S \otimes V} V \otimes V \to V$ can cancel to $V \to k \to V$.

• Interesting, very interesting indeed! – baharampuri Jul 24 '15 at 7:29
• dmtcs.org/pdfpapers/dmAO0146.pdf this might be of interest. This article gives a formula for the antipode in a special case, for the general you may see : google.co.in/… – baharampuri Jul 24 '15 at 7:31
• Thank you. It contains the answer on page 519. So feel free to make this an answer. – Martin Brandenburg Jul 24 '15 at 7:33

• So the formula is: If $G$ is a graph, then $S(G)=\sum_{\pi} (-1)^{|\pi|} |\pi|! G_{\pi}$, where the sum runs over all ordered partitions $\pi$ of $V(G)$ into nonempty sets, and $G_{\pi}$ is the disjoint union of the induced subgraphs. – Martin Brandenburg Jul 24 '15 at 8:24