Cycle covering in bridgeless graphs
type: Item
instance of: scholarly article
title: Cycle covering in bridgeless graphs
zbMATH Open document ID: 0583.05035
DOI: 10.1016/0095-8956(85)90044-9
author: Pierre Fraisse
published in: Journal of Combinatorial Theory. Series B
publication date: 1985-01-01T00:00:00Z
review text: A cycle cover of a graph G is a system of cycles of G with the property that each edge of G is contained at least in one of them. A vertex cover of G with cycles is a system of cycles of G such that each vertex of G is contained at least in one of them. The length of such a cover is the sum of lengths of all of its cycles. (If weights are assigned to edges, then the length of a circuit is the sum of weights of all its edges; otherwise it is the number of edges.) For graphs with weighted edges it is proved that every bridgeless graph G admits a cycle cover of length at most \(m+5| t| /4\), where m is the number of edges and \(| t|\) is the maximal sum of weights of edges of a spanning tree of G. Every bridgeless graph G without weights of edges admits a cycle cover of length at most \(m+5(n-1)/4\), where n is the number of vertices of G. If G is a graph such that every vertex lies in a cycle, then G has a vertex cover with cycles of length at most 50(n- 1)/23. Some problems and conjectures are proposed.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3933109
zbMATH Keywords: vertex cover with cycles
zbMATH Keywords: weight of an edge
zbMATH Keywords: cycle cover of a graph
zbMATH Keywords: weighted edges
zbMATH Keywords: bridgeless graph
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
full work available at URL: 0095-8956(85)90044-9
OpenAlex ID: W2086333030
cites work: Shortest coverings of graphs with cycles
cites work: Q4096964
cites work: Q3097395
cites work: Q4166786
cites work: On Minimal Blocks
cites work: Lectures on matroids
description: scientific article; zbMATH DE number 3933109