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
    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

    Identifiers