The construction and reduction of strong snarks (Q1356495)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The construction and reduction of strong snarks
scientific article

    Statements

    The construction and reduction of strong snarks (English)
    0 references
    6 August 1997
    0 references
    Let \(G\) be a 2-connected cubic graph and \(w: E(G) \mapsto \{ 1, 2 \}\) such that the weight 2 edges form a perfect matching of the graph \(G\). An ordered pair \((G, w)\) is called a strong snark if \(G\) does not have a faithful circuit cover with respect to the weight \(w\) (note that a strong snark is also called a contra pair by \textit{B. Alspach et al.} in [Trans. Am. Math. Soc. 344, No. 1, 131-154 (1994; Zbl 0810.05043)] and by the reviewer in the book [Integer flows and cycle covers of graphs (1996; Zbl 0866.05001)]. Some reduction methods were studied in the paper for strong snarks with small edge cuts (with at most 5 edges and total weight at most 6). Some reverse processes were also studied for the construction of larger strong snarks (in which there are some small edge cuts).
    0 references
    circuit cover
    0 references
    snark
    0 references
    0 references

    Identifiers