A note on fundamental, non-fundamental, and robust cycle bases

Konstantin Klemm, Peter F. Stadler

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

In many biological systems, robustness is achieved by redundant wiring, and reflected by the presence of cycles in the graphs connecting the systems' components. When analyzing such graphs, cyclically robust cycle bases of are of interest since they can be used to generate all cycles of a given 2-connected graph by iteratively adding basis cycles. It is known that strictly fundamental (or Kirchhoff) bases, i.e., those that can be derived from a spanning tree, are not necessarily cyclically robust. Here we note that, conversely, cyclically robust bases (even of planar graphs) are not necessarily fundamental. Furthermore, we present a class of cubic graphs for which cyclically robust bases can be explicitly constructed.

Original languageEnglish
Pages (from-to)2432-2438
Number of pages7
JournalDiscrete Applied Mathematics
Volume157
Issue number10
DOIs
Publication statusPublished - May 28 2009

Keywords

  • Cycle basis
  • Cyclically robust basis
  • Fundamental cycle basis

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A note on fundamental, non-fundamental, and robust cycle bases'. Together they form a unique fingerprint.

Cite this