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 -