A service provided by the WU Library and the WU IT-Services

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

Download (210Kb) | Preview


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 16:10
Last Modified: 20 Aug 2018 17:02
Related URLs:
FIDES Link: https://bach.wu.ac.at/d/research/results/51787/
URI: http://epub.wu.ac.at/id/eprint/6469


View Item