On shortest cocycle covers of graphs
type: Item
instance of: scholarly article
title: On shortest cocycle covers of graphs
zbMATH Open document ID: 0584.05051
DOI: 10.1016/0095-8956(85)90045-0
author: François Jaeger
author: Abdelkader Khelladi
author: Michel Mollard
published in: Journal of Combinatorial Theory. Series B
publication date: 1985-01-01T00:00:00Z
review text: Let G be a graph having vertex set V and edge set E. If \(S\subseteq V\), then the cocycle of G defined by S, denoted by \(\omega_ G(S)\), is the set of edges of G with exactly one end in S. A cocycle of G is any set of edges of the form \(\omega_ G(S)\) for some \(S\subseteq V\). A cocycle cover of the graph G is a family C of cocycles of G such that each edge of G belongs to at least one member of C. Further, the length of C, denoted by \(\ell (C)\), is the sum of the cardinalities of its members. The authors point out that for a loopless graph G, having edge set E, a cocycle cover C has length less than \(2| E|\). The authors further show that there exists no \(\alpha <2\) such that every loopless graph with edge set E has a cocycle cover with length at most \(\alpha\) \(| E|\). To accomplish this it is shown that the minimum length of all cocycle covers, of the complete graphs of order n, is \((n-1)^ 2\) for \(n>8\).
reviewed by: Ortrud R. Oellermann
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3935090
zbMATH Keywords: cocycle cover
MaRDI profile type: Publication
full work available at URL: 0095-8956(85)90045-0
OpenAlex ID: W2021160321
cites work: Q5615282
cites work: Q3097395
cites work: Q4166786
cites work: Covering Graphs by Simple Circuits
cites work: Shortest coverings of graphs with cycles
cites work: Nowhere zero flow and circuit covering in regular matroids
description: scientific article; zbMATH DE number 3935090