A note on quasi-robust cycle bases

Ostermeier, Philipp-Jens and Hellmuth, Marc and Klemm, Konstantin and Leydold, Josef and Stadler, Peter F. (2009) A note on quasi-robust cycle bases. Ars Mathematica Contemporanea, 2. pp. 213-240. ISSN 1855-3974

Available under License Creative Commons Attribution 3.0 Austria (CC BY 3.0 AT).

Download (215kB)


We investigate here some aspects of cycle bases of undirected graphs that allow the iterative construction of all elementary cycles. We introduce the concept of quasi-robust bases as a generalization of the notion of robust bases and demonstrate that a certain class of bases of the complete bipartite graphs K m,n with m,n _> 5 is quasi-robust but not robust. We furthermore disprove a conjecture for cycle bases of Cartesian product graphs.

Item Type: Article
Additional Information: This work was partially supported by a grant of the DFG (Proj No. STA850/5-1) and the Volkswagen-Stiftung.
Keywords: Cycle space, cycle basis, robust, quasi-robust, Kainen's basis, elementary cycle, complete bipartite, Cartesian product
Classification Codes: Math. Subj. Class.: 05C10
Divisions: Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Forschungsinstitute > Rechenintensive Methoden
Version of the Document: Published
Depositing User: Gertraud Novotny
Date Deposited: 20 Aug 2018 14:10
Last Modified: 20 Aug 2018 15:02
Related URLs:
FIDES Link: https://bach.wu.ac.at/d/research/results/51787/
URI: https://epub.wu.ac.at/id/eprint/6469


View Item View Item


Downloads per month over past year

View more statistics