The lattice of cycles of an undirected graph

DOI10.1016/J.LAA.2020.10.027MaRDI QIDQ2228498zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 17 February 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.01001

zbMATH Keywords

abelian groupalgorithmic complexitycycle latticegraph algorithmsgraph cycleslattice basislinear hullundirected graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Abstract: 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 classical results for the vector space of cycles of a graph over the binary field to the case of an arbitrary field.

Recommendations

• Minimum Cycle Bases in Graphs Algorithms and Applications
• Minimum cycle bases, faster and simpler
• Minimum Cycle Bases and Their Applications
• Is every cycle basis fundamental?
• Cycle bases in graphs characterization, algorithms, complexity, and applications

Cites work

• A Reduction Method for Edge-Connectivity in Graphs
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Expander graphs and their applications
• Graph theory
• scientific article; zbMATH DE number 3728302 (Why is no real title available?)
• scientific article; zbMATH DE number 67325 (Why is no real title available?)
• scientific article; zbMATH DE number 475604 (Why is no real title available?)
• scientific article; zbMATH DE number 863470 (Why is no real title available?)
• Matching structure and the matching lattice
• On Hilbert bases of cuts
• On the distribution of cycle lengths in graphs
• On the number of sets of cycle lengths
• Shortest coverings of graphs with cycles
• The diameter of a scale-free random graph
• The number of cycle lengths in graphs of given minimum degree and girth

Cited in

(6)

• Sparse representation of vectors in lattices and semigroups
• A determinantal formula for circuits of integer lattices
• scientific article; zbMATH DE number 4055651 (Why is no real title available?)
• Lattice graphs with non-concurrent longest cycles
• (p,q)-odd digraphs
• STACS 2004

This page was built for publication: The lattice of cycles of an undirected graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2228498)