TY - JOUR

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

AU - Klemm, Konstantin

AU - Stadler, Peter F.

N1 - Funding Information:
We thank Andreas Dress for valuable comments on this manuscript. The work has been supported by a grant from the VolkswagenStiftung.

PY - 2009/5/28

Y1 - 2009/5/28

N2 - 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.

AB - 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.

KW - Cycle basis

KW - Cyclically robust basis

KW - Fundamental cycle basis

UR - http://www.scopus.com/inward/record.url?scp=67349251551&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67349251551&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2008.06.047

DO - 10.1016/j.dam.2008.06.047

M3 - Article

AN - SCOPUS:67349251551

VL - 157

SP - 2432

EP - 2438

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 10

ER -