Subgraph coverings and edge switchings
type: Item
instance of: scholarly article
title: Subgraph coverings and edge switchings
zbMATH Open document ID: 1031.05104
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: The author proves that the edges of a connected graph \(G\) can be covered with at most \(\lceil n/2\rceil\) paths, a result conjectured by Chung. He also proves a conjecture of Bondy which states that, if \(G\) is \(2\)-connected, then its edges can be covered by at most \(\lceil (2n-1)/3\rceil\) circuits. With the weaker assumption that \(G\) is \(2\)-edge connected he shows that there is a covering with at most \(\lceil 3(n-1)/4\rceil\) circuits. All bounds are tight.
reviewed by: Oriol Serra
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1843801
zbMATH Keywords: path coverings
zbMATH Keywords: circuit coverings
author: Genghua Fan
MaRDI profile type: Publication
full work available at URL: jctb.2001.2063
OpenAlex ID: W2075800592
cites work: Q3360905
cites work: Q5422499
cites work: On the coverings of graphs
cites work: An upper bound for the path number of a graph
cites work: The Representation of a Graph by Set Intersections
cites work: Q5539649
cites work: An Erdős-Gallai conjecture
cites work: Covering the edges of a connected graph by paths
DOI: 10.1006/JCTB.2001.2063
description: scientific article; zbMATH DE number 1843801