Shortest circuit covers of cubic graphs (Q1322025)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Shortest circuit covers of cubic graphs |
scientific article |
Statements
Shortest circuit covers of cubic graphs (English)
0 references
26 January 1995
0 references
The paper provides a constructive proof that the edge set of a bridgeless cubic graph \(G\) can be covered by circuits with lengths summing to at most \({64 \over 39} | E(G) |\). The proof technique indicates a polynomial algorithm for finding such a circuit cover. Improvements for cubic graphs of larger girth are included.
0 references
cycles covers
0 references
cubic graph
0 references
polynomial algorithm
0 references
circuit cover
0 references
