A note on quasi-robust cycle bases

Philipp-Jens Ostermeier, Marc Hellmuth, Josef Leydold, Konstantin Klemm, Peter F. Stadler

Abstract


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 Km,n with m, n ≥ 5 is quasi-robust but not robust. We furthermore disprove a conjecture for cycle bases of Cartesian product graphs.

Keywords


Cycle space, Cycle basis, robust, quasi-robust, Kainen's Basis, elementary cycle, complete bipartite, Cartesian product

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.104.5b7

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications