A Hopf algebra for counting cycles

作者：Giscard Pierre Louis^*; Rochet Paul; Wilson Richard C

来源：Discrete Mathematics, 2018, 341(5): 1439-1448.

DOI：10.1016/j.disc.2017.10.002

• Cycles
• Induced subgraph
• Hopf algebra
• Trace monoid

Cycles, also known as self-avoiding polygons, elementary circuits or simple cycles, are closed walks which are not allowed to visit any vertex more than once. We present an exact formula for enumerating such cycles of any length on any directed graph involving a sum over its induced subgraphs. This result stems from a Hopf algebra, which we construct explicitly, and which provides further means of counting cycles. Finally, we obtain a more general theorem asserting that any Lie idempotent can be used to enumerate cycles.

• 出版日期2018-5