Shortest circuit covers of cubic graphs
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.
scientific article; zbMATH DE number 562411