The construction and reduction of strong snarks

DOI10.1016/S0012-365X(96)00256-7MaRDI QIDQ1356495zbMATH OpenFDO

Publication date 6 August 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(96)00256-7

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Review text

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

Recommendations

Cites work

Cited in

(4)

This page was built for publication: The construction and reduction of strong snarks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356495)