Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903028 | Discrete Mathematics | 2018 | 10 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Pierre-Louis Giscard, Paul Rochet, Richard C. Wilson,