Interchangeability of relevant cycles in graphs

MaRDI QIDQ1972676zbMATH OpenFDO

Authors Petra M. Gleiss, Josef Leydold, Peter F. Stadler

Publication date 16 April 2000

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/120353, http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r16.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

minimum cycle basisrelevant cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Protein sequences, DNA sequences (92D20) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Review text

Summary: The set \(\mathcal{R}\) of relevant cycles of a graph \(G\) is the union of its minimum cycle bases. We introduce a partition of \(\mathcal{R}\) such that each cycle in a class \(\mathcal{W}\) can be expressed as a sum of other cycles in \(\mathcal{W}\) and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class \(\mathcal{W}\). This result is used to derive upper and lower bounds on the number of distinct minimum cycle bases. Finally, we give a polynomial-time algorithm to compute this partition.

Recommendations

• Union of all the minimum cycle bases of a graph
• Minimum Cycle Bases in Graphs Algorithms and Applications
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Minimum Cycle Bases and Their Applications

Cited in

(3)

• Union of all the minimum cycle bases of a graph
• Minimum Cycle Bases and Their Applications
• Computing cyclic invariants for molecular graphs

This page was built for publication: Interchangeability of relevant cycles in graphs

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