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