The lattice of cycles of an undirected graph

Gennadiy Averkov, Anastasia Chavez, Jesus A. De Loera, Bryan R. Gillespie

Published 2020-02-03Version 1

We study bases of the lattice generated by the cycles of an undirected graph, defined as the integer linear combinations of the 0/1-incidence vectors of cycles. We prove structural results for this lattice, including explicit formulas for its dimension and determinant, and we present efficient algorithms to construct lattice bases, using only cycles as generators, in quadratic time. By algebraic considerations, we relate these results to the more general setting with coefficients from an arbitrary Abelian group. Our results generalize old classical results for the vector space of cycles of a graph over the binary field to the case of an arbitrary field.