×

zbMATH — the first resource for mathematics

Classification of robust cycle bases and relations to fundamental cycle bases. (English) Zbl 1421.05034
Summary: The construction of a cycle in a graph can be realized by iteratively adding cycles of a cycle basis. The construction of each elementary cycle is only possible if this cycle basis is robust. In the last years, different classes of robust cycle bases have been established. We compare these classes and show that they are completely unrelated. More precisely, we draw a Venn diagram which displays the obvious containedness relations and show that each of its regions is not empty. In addition, we continue the comparison with fundamental cycle bases.
MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Software:
LEDA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] C. Champetier, On the null-homotopy of graphs, Discrete Math. 64 (1987), 97-98, doi:10. 1016/0012-365x(87)90244-5.
[2] U. Do¯grus¨oz and M. S. Krishnamoorthy, Enumerating all cycles of a planar graph, Parallel Algorithms Appl.10 (1996), 21-36, doi:10.1080/10637199608915603.
[3] P. Duchet, M. Las Vergnas and H. Meyniel, Connected cutsets of a graph and triangle bases of the cycle space, Discrete Math. 62 (1986), 145-154, doi:10.1016/0012-365x(86)90115-9. · Zbl 0609.05032
[4] P. M. Gleiss, Short Cycles, Ph.D. thesis, Universit¨at Wien, 2001,https://www.tbi. univie.ac.at/papersold/papers/Abstracts/pmg_diss.pdf.
[5] D. Hartvigsen and E. Zemel, Is every cycle basis fundamental?, J. Graph Theory 13 (1989), 117-137, doi:10.1002/jgt.3190130115. · Zbl 0699.05031
[6] P. C. Kainen, On robust cycle bases, Electron. Notes Discrete Math. 11 (2002), 430-437, doi: 10.1016/s1571-0653(04)00087-3. · Zbl 1075.05555
[7] P. C. Kainen, Cycle construction and geodesic cycles with application to the hypercube, Ars Math. Contemp.9 (2015), 27-43,http://amc-journal.eu/index.php/amc/ article/view/450. · Zbl 1329.05162
[8] K. Klemm and P. F. Stadler, A note on fundamental, non-fundamental, and robust cycle bases, Discrete Appl. Math.157 (2009), 2432-2438, doi:10.1016/j.dam.2008.06.047. · Zbl 1163.92002
[9] C. Liebchen, Periodic Timetable Optimization in Public Transport, Ph.D. thesis, Technische Universit¨at Berlin, 2006. · Zbl 1209.90095
[10] K. Mehlhorn and S. N¨aher, LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, Cambridge, 1999,https://people.mpi-inf.mpg.de/ ˜mehlhorn/LEDAbook.html.
[11] P.-J.Ostermeier,Quasi-robustCycleSpaces,2009,http://www.bioinf. uni-leipzig.de/conference-registration/09herbst/talks/401_ Ostermeier.pdf(accessed on 4 October 2017).
[12] P.-J. Ostermeier, M. Hellmuth, K. Klemm, J. Leydold and P. F. Stadler, A note on quasi-robust cycle bases, Ars Math. Contemp. 2 (2009), 231-240,http://amc-journal.eu/index. php/amc/article/view/104. · Zbl 1216.05019
[13] A. Reich, Cycle Bases of Graphs and Spanning Trees with Many Leaves, Ph.D. thesis, Brandenburgische Technische Universit¨at Cottbus - Senftenberg, 2014,https://opus4.kobv. de/opus4-btu/files/2966/Dissertation_Reich.pdf. 18Art Discrete Appl. Math. 1 (2018) #P1.03
[14] M. M. Sysło, On cycle bases of a graph, Networks 9 (1979), 123-132, doi:10.1002/net. 3230090203.
[15] G. W¨unsch, Coordination of Traffic Signals in Networks and Related Graph Theoretical Problems on Spanning Trees, Ph.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.