Interchangeability of relevant cycles in graphs
type: Item
instance of: scholarly article
title: Interchangeability of relevant cycles in graphs
zbMATH Open document ID: 0939.05048
author: Petra M. Gleiss
author: Josef Leydold
author: Peter F. Stadler
published in: The Electronic Journal of Combinatorics
publication date: 2000-04-16T00:00:00Z
full work available at URL: https://eudml.org/doc/120353
full work available at URL: v7i1r16.html
review text: Summary: The set \(\mathcal{R}\) of relevant cycles of a graph \(G\) is the union of its minimum cycle bases. We introduce a partition of \(\mathcal{R}\) such that each cycle in a class \(\mathcal{W}\) can be expressed as a sum of other cycles in \(\mathcal{W}\) and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class \(\mathcal{W}\). This result is used to derive upper and lower bounds on the number of distinct minimum cycle bases. Finally, we give a polynomial-time algorithm to compute this partition.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 92E10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 92D20
zbMATH DE Number: 1431767
zbMATH Keywords: minimum cycle basis
zbMATH Keywords: relevant cycles
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1431767