Subgraph coverings and edge switchings (Q1850576): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.2001.2063 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2075800592 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3360905 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the coverings of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An upper bound for the path number of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Representation of a Graph by Set Intersections / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5539649 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Erdős-Gallai conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Covering the edges of a connected graph by paths / rank | |||
Normal rank |
Latest revision as of 19:11, 4 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Subgraph coverings and edge switchings |
scientific article |
Statements
Subgraph coverings and edge switchings (English)
0 references
10 December 2002
0 references
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.
0 references
path coverings
0 references
circuit coverings
0 references